Introduction Exponential Time Algorithms
60
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
60
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Exponential time algorithms S. Gaspers Introduction Exponential Time Algorithms Problem Definitions Algorithm Design Techniques Dynamic Programming across Subsets Branch & Reduce Memorization Treewidth Treewidth combined with Branch & Reduce Iterative Compression Inclusion-Exclusion Conclusion Introduction to Exponential Time Algorithms séminaire AlGco Serge Gaspers1 1LIRMM – Université Montpellier 2, CNRS January 22, 2009 1 / 50
Voir
- exponential time
- iterative compression
- treewidth
- inclusion-exclusion
- algorithms
- reduce
- hard problems
- algorithm design
Introduction to Exponential Time Algorithms séminaire AlGco
January 22, 2009
1LIRMM – Université Montpellier 2, CNRS
/105
Serge Gaspers1
1
Introduction Exponential Time Algorithms Problem Definitions
Conclusion
3
Algorithm Design Techniques Dynamic Programming across Subsets Branch & Reduce Memorization Treewidth Treewidth combined with Branch & Reduce Iterative Compression Inclusion-Exclusion
2
Outline
50/2
3
1
2
Conclusion
Outline
Algorithm Design Techniques Dynamic Programming across Subsets Branch & Reduce Memorization Treewidth Treewidth combined with Branch & Reduce Iterative Compression Inclusion-Exclusion
0
Introduction Exponential Time Algorithms Problem Definitions
5/3spersIntthmsS.GaemlaogirneitlaitEonxp
NP-hard problems
50
no known polynomial time algorithm for any NP-hard problem belief:P6=NP ETH: 3-Sat cannot be solved in subexponential time (thus many other problems cannot be solved in subexponential time either)
Approaches to attack NP-hard problems approximation algorithms randomized algorithms fixed parameter algorithms exact exponential time algorithms heuristics restricting the inputs
Dealing with NP-hard problems
05/5Coonlunconsi
natural question in Algorithms: design faster (worst-case analysis) algorithms for problems might lead to practical algorithms for small instances subroutines for (sub)exponential time approximation algorithms randomized algorithms with expected polynomial run time interesting combinatorics
Exponential Time Algorithms
6/5Epxalgotimetialonenuced&RchanBrthwidenibmochtdiweerdthTeewionTrzatiomireceMeRudcn&honcnoCisululcxnoislusion-EssionIncevoCpmerIeetaritborPsmhtinfieDmelTialtienrigoAlmeudtctnorpxnooiEnmsS.rithersIGasporcauSsstesbarBsminarocPamgrngmiisngeThcinuqseyDtionsAlgorithmDe
