DMI018 - Aproximační a online algoritmy

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

ZS 2001 - Jiří Sgall

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
modely pravděpodobnostních on-line algoritmů a jejich vztahy

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í

relaxace pomocí semidefinitního programování
derandomizace pomocí částečně nezávislých náhodných proměnných a metodou podmíněných pravděpodobností

problém obchodního cestujícího

1.5 aproximační algoritmus
PTAS v rovině

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

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
paging s velikostí a cenou stránek (přehled)

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
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í algoritmus pro dva identické počítače
horní odhad pro deterministické a pravděpodobnostní algoritmy na počítačích různých rychlostí
dolní odhad 2 pro preemptivní rozvrhování na počítačích různých rychlostí