|
|
Algorithms for Low Highway Dimension Graphs
Vu, Tung Anh ; Feldmann, Andreas Emil (vedoucí práce) ; Lampis, Michail (oponent)
V této práci navrhneme algoritmy pro problém k-Supplier with Outliers. V síti dostaneme zadanou množinu dodavatelů a množinu klientů. Cílem je vybrat k doda- vatelů tak, aby vzdálenost mezi každým obslouženým klientem a nejbližším vybraným dodavatelem byla co nejmenší. Je dovoleno ponechat některé klienty neobsloužené. Max- imální počet klientů, které nemusíme obsloužit, je dán na vstupu. Jelikož k-Supplier with Outliers má mnoho využití v logistice, soustředíme se na parametry, které jsou vhodné pro dopravní sítě. Zabýváme se grafy s malou highway dimension, která byla zavedena Abrahamem et al. [SODA 2010] a grafy s malou doubling dimension. Je známo, že za předpokladu P ̸= NP nelze pro žádné kladné ε problém k-Sup- plier with Outliers (3 − ε)-aproximovat. Problém k-Supplier with Outliers je W[1]-těžký pro grafy s konstantní doubling dimension a highway dimension. Oba tyto těžkostní výsledky překonáme pomocí paradigmatu parametrizovaných aproximačních algoritmů. V případě highway dimension navrhneme (1 + ε)-aproximační algoritmus pro jakéko- liv kladné ε pracující v čase f(k, p, h, ε) · nO(1) , kde p je povolený počet klientů, které nemusíme obsloužit, h je highway dimension grafu na vstupu a f je nějaká vyčíslitelná funkce. V případě doubling dimension navrhneme (1 + ε)-aproximační algoritmus pro...
|
host ::
RSS.