NDMI018 - Aproximační a online algoritmy - Probraná témata
LS 2008 - Jiří Sgall
Základní pojmy a metody
- 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álové funkce pro online algoritmy
Aproximační algoritmy
- obchodní cestující: 1.5 aproximační algoritmus, O(log n) aproximace pro asymetrickou verzi
- Steinerův strom, 2-aproximace
- 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čů
- 2-aproximace pro počítače s nezávislými rychlostmi
- "téměř" aproximační schéma pro bin-packing, first fit algoritmus
- preemptivní rozvrhování na počítačích různých rychlostí
- PCP věta a její použití pro důkaz NP-těžkosti aproximace
Online algoritmy
- 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 a dolní odhad
- vážené a další zobecněné varianty, přehled výsledků
- 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 (bez důkazu)
- online rozvrhování
- 4/3 kompetitivní algoritmus pro dva identické počítače
- horní odhad pro preemptivní 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í
- navigace
- prohledávání přímky (cow path), optimální
deterministický
a pravděpodobnostní algoritmus
- problém zdi, dolní odhad a deterministický O(n1/2)-kompetitivní
algoritmus
- problém pokoje a navigace z bodu do bodu, O(n1/2)-kompetitivní
algoritmus
Kontakt: sgall@math.cas.cz, 222 090 780
Zkoušky
se konají v mé pracovně v Matematickém ústavu. Adresa je Žitná
25,
u křižovatky se Štěpánskou. Projdete průchodem, rovně přes dvůr do tzv.
zadní budovy, v přízemí vlevo od výtahu (stejné jako do posluchárny) zazvoníte na můj zvonek.
Termíny: Zkouška se koná ve středu 18.
6. v 10 hodin, nejlepe se ještě ohlašte mailem. Na jiných termínech se
podle potřeby dohodneme individuálně mailem.
Literatura
Pro aproximační algoritmz doporučuji poznámky Williamsona a knihu
Vaziraniho. Pro online algoritmy pro paging a k-server problem knihu
Borodin, El-Yaniv. Dále přikládám odkazy na články o navigaci a
rozvrhování, vesměs věci, které jsme probrali jen nepořádně na poslední
přednášce. V mém přehledu je sepsaný důkaz 4/3-kompetitivního algoritmu
pro 2 počítače, v dalších dvou pak dolní a horní odhad na preemptivní
rozvrhování na počítačích různých rychlostí.
Lecture notes (online)
David Williamson - kurs aproximačních algoritmů: http://www.math.cas.cz/~sgall/teach/dw-notes2.ps
Avrim Blum - obdobný kurs: http://www-2.cs.cmu.edu/~avrim/Approx00/
Yossi Azar - obdobný kurs: http://www.cs.tau.ac.il/~azar/online03.html
Knihy
V.V. Vazirani: Approximation Algorithms, Springer, 2001.
J. Hromkovic: Algorithmics for Hard Problems, Springer, 2001.
G. Ausiello et al: Complexity and Approximation, Springer, 1999.
D.S. Hochbaum (editor): Approximation algorithms for NP-hard problems,
PWS publishing company, 1997.
A. Borodin, R. El-Yaniv: Online computation and competitive analysis.
Cambridge university press, 1998.
A. Fiat, G. Woeginger: Online Algorithms - The State of the Art,
LNCS 1442, Springer, 1998.
Články
A. Blum, P. Raghavan, and B. Schieber. Navigating in Unfamiliar Geometric
Terrain. Siam J.
Comp 26(1):110-137, February 1997. An earlier version
appears in Proceedings
of the 23rd Annual ACM Symposium on Theory of Computing, pages
494-504, May 1991.
J. Sgall: On-line scheduling
In Online Algorithms: The State of the Art, eds.A. Fiat and G.
J.
Woeginger, Lecture Notes in Comput. Sci. 1442, pages 196-231, Springer,
1998.
L. Epstein, J. Sgall: A lower bound for on-line scheduling on
uniformly related machines
Oper. Res. Lett., 26(1):17-22, 2000.
T. Ebenlendr, J. Sgall: Optimal and online preemptive scheduling on
uniformly related machines
In Proc. of the 21st Ann. Symp. on Theor. Aspects of Comput.
Sci. (STACS) , Lecture Notes in Comput. Sci. 2996, pages 199-210.
Springer, 2004.