DMI018 - Aproximační a online algoritmy - Probraná témata

• 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
• 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í
• relaxace pomocí semidefinitního programování
• derandomizace metodou podmíněných pravděpodobností
• použití potenciální funkce pro online algoritmy

• problém obchodního cestujícího
  
  • 1.5 aproximační algoritmus,
    
  • O(log n) aproximace 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: aproximační algoritmus pomocí semidefinitního programování
• splnitelnost: 3/4-aproximační algoritmus pro MAX-SAT, varianty pro podtřídy formulí
  
• problémy rozvrhování a bin-packing
• hladový algoritmus, zlepšení při uspořádání úloh, a (F)PTAS pro identické počítačů
• "téměř" aproximační schéma pro bin-packing, first fit algoritmus
• preemptivní rozvrhování na počítačích různých rychlostí
• aproximační algoritmus pro rozvrhování  na "unrelated" počítačích
  
• PCP věta a její použití pro důkaz NP-těžkosti aproximace

• online rozvrhování
• 4/3 kompetitivní algoritmus pro dva identické počítače
• dolní odhad pro identické počítače a pro počítače různých rychlostí
  
• horní odhad pro deterministické a pravděpodobnostní algoritmy na počítačích různých rychlostí
• problém půjčování lyží (ski rental): optimální deterministický a pravděpodobnostní algoritmus
• cachování (paging)
  
• k-kompetitivní deterministické algoritmy a dolní odhad
• O(log k)-kompetitivní pravděpodobnostní algoritmus
• k-server problém
• dolní odhad k na kompetitivní poměr pro libovolné metrické prostory
• výpočet optimálního řešení (off-line), work function a WFA (work function algoritmus)
• optimální deterministický online algoritmus pro stromy
• harmonický algoritmus, exponenciální horní odhad
  
• navigace
• prohledávání přímky (cow path), optimální deterministický a pravděpodobnostní 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