Aproximační algoritmy pro metrické problémy

• Název práce v češtině: Aproximační algoritmy pro metrické problémy
• Název v anglickém jazyce: Approximation algorithms for metric problems
• Klíčová slova: aproximační algoritmy; metrické problémy; lineární programování
• Klíčová slova anglicky: approximation algorithms; metric problems; linear programming
• Akademický rok vypsání: 2019/2020
• Typ práce: disertační práce
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. RNDr. Jiří Sgall, DrSc.

Zásady pro vypracování

Cílem práce je navrhnout a analyzovat nové aproximační algoritmy metrické problémy jako je problém obchodního cestujícího. Metody mohou zahrnovat relaxace pomocí lineárního programování, grafově-teoretické metody i analýzu a dekompozici metrických prostorů.

Seznam odborné literatury

D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.

Aktuální konferenční a časopisecké články