Introduction Exponential Time Algorithms

Time Algorithms

Description

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

• exponential time


• iterative compression


• treewidth


• inclusion-exclusion


• algorithms


• reduce


• hard problems


• algorithm design

Sujets

• Algorithm
• University of Montpellier
• Time complexity
• Tree decomposition
• Inclusion?exclusion principle
• Reduce
• Algorithm design

Informations

• Publié par: pefav
• Nombre de lectures: 42
• Langue: English

Extrait

Exponentialtime laogirhtsm .SaGpss I er rontctdun E io nopxitneiTla lA em thmsgori lemDProbitnofiein rotiA s glgnsiDehm qunichTe imanyD se margorPc ssuSsbte imgn caor Reduce Me s Branch& rT no iwee iromitaz thidmbco h T dt ewre hcR&rBnaiwht nide veCorati e Ite educ isulcnI noisserpm ncCo onsiluxc-Eon siluon

Introduction to Exponential Time Algorithms séminaire AlGco

January 22, 2009

1 LIRMM – Université Montpellier 2, CNRS

/105

Serge Gaspers 1

poEx aspers In ithms S.G mi a e glro entnaitl itorlg e A imlTiantenopxE noitcudort mDesrithAlgo ionsnfitimeeDorlb mh P s ubsSoscr anBr tsse cudeR&hc ziromeM e echn ign Ts Dyn ique rPgomacini a garmm hBitncraReh&cedu retIvitamoCeserp ation Treewidth Treeiwtdchmoiben w d n -nxEsuoinIlc isno usiooncl ion C clus

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

Dyna queschni gn Te gn ca maimorrgimPc ncra s B etbsSussro aziromeM ecudeR&h n Exponen roductio lAogirht itlaiTem efimDtiniPr ms leob mhtiiseDA sno rogl cnul oi I n E-cxisnoon Co lusi sionnclu itno rTeeiwtd T h erewidthcombined wirBhthcnadeR& I ecu ratevetimpCossre

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/3 spers Int thms S.Ga em laogir neitlaitEonxp

finDeioitro s Pembl DmhtgiselA sn irog Exponent oduction glrotimh aiTlmi A e itorlg e a imltiant rtnI srepsaG.S smh openxE arBh&hcnudeR tI ec atereCivpromsies oi T n erwediht rTeewidthcombined wit esbuSsso hcnarB st e M uced&R atizorem nhqiT n ce nyma eu D s ograicPrg acr mmin noisulcnoC noisuclExn-iousclIn on 4/

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)

ranch&Re Subsets B gn caorss orrgmaim re h Tidew eeTrdtwi azirnoit ecud omeM tera uce I &RedanchhtrB de iw bmnihtoc siluxc-EonsiluncI noisserpmoCevit laitem laogirhtsm Exponenti oitc pxE n nenolait GaS.ersp nt s Iduro Dmfieboelno A sinit Algo Time ms Pr rith seuqinhc PcimanyD hmitorlg Te gnsiDe

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/5 Co on lunconsi

0

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/5 Epx algo timetialonen uced&RchanBrthwi denibmochtdiweer dth T eewi on Tr zatiomir ec eM eRudcn&h oncnoCisul ulcxnoislusion-E ssion Inc evoCpmerI e etarit borP smht infieDmel Tialtien rigoAl me udtctnor pxno oi E n ms S. rith ers I Gasp orcauSsstesb arB s minarocPamgrngmi isng eThcinuqse yD tions AlgorithmDe