I396 - Aproximační a online algoritmy

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

ZS 1999 - 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

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í

problém ruksaku, rozvrhování a bin-packing

PTAS pro problém ruksaku a 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

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

O(log k)-aproximační algoritmus pro speciální případ stejné ceny všech stránek

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í dynamickým programováním (off-line)
WFA (work function algoritmus), definice bez důkazů
optimální deterministický online algoritmus pro stromy

navigace

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
prohledávání přímky (cow path), optimální deterministický a pravděpodobnostní online algoritmy

online rozvrhování na počítačích různých rychlostí

horní odhad pro deterministické a pravděpodobnostní algoritmy
dolní odhad 2 pro preemptivní rozvrhování