DMI018 - Aproximační a online algoritmy - Probraná témata
LS 2006 - 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
- 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í
- PCP věta a její použití pro důkaz NP-těžkosti aproximace
Online algoritmy
- online rozvrhování
- 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 (bez důkazu)
- navigace
- prohledávání přímky (cow path), optimální
deterministický
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
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, ve 2. patře zazvoníte na dveře vpravo
(s cedulkou Matematický ústav).
Zatím jsou vypsané termíny čtvrtek 1. 6. a středa 28. 6., vždy od 13
hod. Další případně po domluvě mailem.
Kontakt: sgall@math.cas.cz, 222 090 780