NDMI018 - Aproximační a online algoritmy

LS 2010 - Jiří Sgall

Úkoly a cvičení

• 1. série úkolů (termín 17. 3.)
• 2. série úkolů (termín 6. 4. nebo na přednášce 7. 4.)
• 3. série úkolů (termín 20. 4. nebo na přednášce 21. 4.)
• 4. série úkolů (termín 4. 5. nebo na přednášce 5. 5.)

Probraná témata

• základní pojmy
• aproximační a kompetitivní poměr, třídy aproximačních algoritmů, PTAS, FPTAS
• vztah NP-úplnosti a silné NP-úplnosti a existence aproximačních algoritmů a schémat
• metody
• dynamické programování a zaokrouhlování
• relaxace pomocí lineárního programování
• zaokrouhlování, pravděpodobnostní zaokrouhlování
• duální řešení LP a jeho použití
• použití duálního řešení pro online algoritmy
  
• relaxace pomocí semidefinitního programování
• derandomizace metodou podmíněných pravděpodobností
• problém obchodního cestujícího a související
  
• 1.5 aproximační algoritmus
• PTAS v rovině
  
• O(log n) aproximační algoritmus pro asymetrickou verzi
• kombinatorické a grafové problémy
• maximální klika a vrcholové pokrytí grafu
• barvení grafů: přibližné barvení 3-obarvitelných grafů
• množinové pokrytí
• hladový algoritmus
• algoritmy založené na lineárním programování
• maximální řez v grafu
• 0.878-aproximační algoritmus pomocí semidefinitního programování
• problém rozvrhování a bin-packing
• hladový algoritmus, zlepšení při uspořádání úloh, a (F)PTAS pro rozvrhování identických počítačů
• "téměř" aproximační schéma pro bin-packing, first fit algoritmus
• splnitelnost a její varianty
• 3/4-aproximační algoritmus pro MAX-SAT, varianty pro speciální případy
• použití semidefinitního programování pro MAX-2SAT
  
• PCP věta a její použití pro důkaz NP-těžkosti aproximace
• problém půjčování lyží (ski rental)
• optimální deterministický a pravděpodobnostní online algoritmus
• paging a jeho varianty
• k-kompetitivní deterministické algoritmy a dolní odhad
• O(log k)-kompetitivní pravděpodobnostní algoritmy a dolní odhad
  
• k-server problém
• dolní odhad k na kompetitivní poměr pro libovolné metrické prostory
  
• definice work function, výpočet optimálního řešení (off-line)
• WFA (work function algoritmus), definice bez důkazů
• optimální deterministický online algoritmus pro stromy
• harmonický algoritmus (bez důkazu)
  
• navigace
• prohledávání přímky (cow path), optimální deterministický a pravděpodobnostní online algoritmus
• problém zdi, dolní odhad a deterministický O(n^1/2)-kompetitivní algoritmus
• problém pokoje a navigace z bodu do bodu, O(n^1/2)-kompetitivní algoritmus
• online rozvrhování
• 4/3 kompetitivní pravděpodobnostní algoritmus pro dva identické počítače
• horní odhad pro deterministické a pravděpodobnostní algoritmy na počítačích různých rychlostí

Probraná látka podle přednášek

• 1. (3. 3.)
  
• úvod, definice apx. poměru
  
• VC 2-apx, i vážené
  
• Nezávislá/klika - porovnání s VC
• zmínění obtížnosti aproximace, unique games conjecture
  
• TSP, 1.5 apx
• 2. (10. 3.)
• rozvrhování
• bin packing
  
• hladové alg. (LIST, LPT pro rozvrhování, FIRST FIT pro bin packing)
• LIST pro rozvrhování se závislostmi
• definice: pseudopolynomiální alg., silně NP-těžké úlohy
• definice: PTAS a FPTAS
  
• 3. (17. 3.)
• vztah FPTAS a silné NP-těžkosti
  
• PTAS pro rozvrhování, FPTAS na konst. počtu počítačů
• asymptotický PTAS pro bin packing
• 4. (25. 3.)
  
• PTAS pro TSP v rovině (bez důkazu)
• ATSP O(log n)
• MAX-SAT 3/4-apx.
• 5. (31. 3.)
• úvod do LP
• množinové pokrytí: primal-dual a analýza hladového algoritmu pomocí LP
  
• semidefinitní programování, úvod
  
• 6. (7. 4.)
• semidefinitní a vektorové programování
• MAXCUT pomocí semidefinitního programování
• MAX-2SAT pomocí semidefinitního programování
• chromatické číslo, sqrt(n) pro 3-chromatické
• 7. (14. 4.)
• chromatické číslo, lepší algoritmy pomocí SDP (náznak)
  
• úvod do online algoritmů, kompetitivní poměr pro deterministické a pravděpodobnostní algoritmy
• problém prohledávání přímky
• problém paging, deterministické horní odhady
• 8. (21. 4.)
• pravděpodobnostní algoritmy pro paging, H_k dolní odhad, 2H_k horní odhad
• k-server problém, definice, dolní odhad k v libovolném metrickém prostroru
  
• 9. (28. 4.)
• k-server problém na stromech
• work function algoritmus pro k-server
• navigace, problém zdi dolní odhad,
• 10. (5. 5.)
  
• navigace, problém zdi a problém pokoje horní odhad
• preemptivní a nepreemptivní rozvrhování na počítačích různých rychlostí pomocí dvojnásobících algoritmů
  
• 11. (19. 5.)
• problém půjčování a kupování (ski rental, buy or rent) pomocí primárně duálního algoritmu pro LP
• online rozvrhování na dvou identických počítačích

Literatura

Lecture notes (online)

Knihy

Články