NDMI018 - Aproximační a online algoritmy

LS 2012 - Jiří Sgall

Úkoly a cvičení

• 1. série úkolů (termín 18. 3. nebo na přednášce 19. 3.)
• 2. série úkolů (termín 10. 4.)
• 3. série úkolů (termín 29. 4. nebo na přednášce 30. 4.)
• 4. série úkolů (termín 13. 5. nebo na přednášce 14. 5.)

Výsledky

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í
• lokální prohledávání
  
• relaxace pomocí lineárního programování
• zaokrouhlování, pravděpodobnostní zaokrouhlování
• duální řešení LP a jeho použití
• primárně duální algoritmy
  
• relaxace pomocí semidefinitního programování
• derandomizace metodou podmíněných pravděpodobností
• potenciál pro online algoritmy
• metody dokazování neaproximovatelnosti
• L-redukce
• PCP věta a její použití, gap preserving redukce
  
• unique games conjecture (znění)
• 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
• zobecněný Steinerův strom - primárně duální algoritmus
  
• kombinatorické a grafové problémy
• maximální klika a vrcholové pokrytí grafu
• 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í
• barvení grafů: přibližné barvení 3-obarvitelných grafů
• kombinatorický algoritmus
• zlepšení 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, derandomizace
  
• použití semidefinitního programování pro MAX-2SAT
  
• 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
• navigace
• prohledávání přímky (cow path), optimální deterministický a pravděpodobnostní online algoritmus
• online rozvrhování
• deterministické a pravděpodobnostní algoritmy na počítačích různých rychlostí - horní a dolní odhady
• online párování v bipartitních grafech
  
• optimální deterministický a pravděpodobnostní algoritmus
  

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

• 1. (27. 2.)
  
• úvod, definice apx. poměru
  
• VC 2-apx, i vážené
  
• TSP, 1.5 apx
• rozvrhování, lokální prohledávání, hladový algoritmus (LIST)
  
• 2. (5. 3.)
• Nezávislá/klika - porovnání s VC
• zmínění obtížnosti aproximace, unique games conjecture
• hladové alg. pro rozvrhování (LIST, LPT)
• definice: pseudopolynomiální alg., silně NP-těžké úlohy
• definice: PTAS a FPTAS
• 3. (12. 3.)
• bin packing, FIRST FIT
• asymptotické PTAS pro bin packing
• PTAS pro TSP v rovině bez důkazu
• úvod do LP, algoritmy pro množinové pokrytí
  
• 4. (19. 3.)
• úvod do LP
• množinové pokrytí: primal-dual a analýza hladového algoritmu pomocí duálu
• obtížnost aproximace, zmíněná unique games conjecture a důsledky pro množinové pokrytí a splnitelnost
• algoritmy pro MAX-SAT: náhodný a zaokrouhlování LP
  
• 5. (26. 3.)
• algoritmy pro MAX-SAT: náhodný výběr ze 2 algoritmů, zaokrouhlování s nelineární funkcí
• derandomizace metodou podmíněných pravděpodobností
  
• semidefinitní a vektorové programování
• MAXCUT pomocí semidefinitního programování
• 6. (2. 4.)
• MAXCUT pomocí SDP, dokončení
  
• chromatické číslo, algoritmus pro obarvení 3-chromatických grafů O(n^1/4) barvami
• 7. (16. 4.)
• nejkratší cesta - Dijkstra jako primárně duální algoritmus
• zobecněný Steinerův strom - 2-aproximační primárně duální algoritmus
• 8. (23. 4.)
• prohledávání přímky deterministicky
• problém paging, deterministické horní odhady
• pravděpodobnostní algoritmy pro paging, 2H_k horní odhad
• 9. (30. 4.)
• pravděpodobnostní algoritmy pro paging, H_k dolní odhad
• k-server problém, definice, přehled výsledků
• k-server problém, dolní odhad k v libovolném metrickém prostroru
• k-server problém na přímce
• 10. (7. 5.)
• k-server problém na stromech
• work function algoritmus pro k-server
• online preemptivní rozvrhování na počítačích různých rychlostí
• horní odhad pro deterministické  algoritmy (dvojnásobící algoritmy)
• 11. (14. 5.)
• online preemptivní rozvrhování na počítačích různých rychlostí
• horní odhad pro pravděpodobnostní algoritmy (dvojnásobící algoritmy)
• dolní odhad pro online rozvrhování na počítačích různých rychlostí (preemptivní i nepreemptivní)
  
• online párování - pravděpodobnostní algoritmus
  
• 12. (21. 5.)
• dokazování neaproximace L-redukcemi
• PCP věta a její použití, gap preserving redukce, příklady
  
• unique games conjecture (znění)
• v domácím úkolu: LPT pro rozvrhování, ATSP, ski renal (půjčování auta)
  

Literatura

Lecture notes (online)

Knihy

Články