|
|
Parameterized Approximations of Directed Steiner Networks
Koreček, Martin ; Feldmann, Andreas Emil (vedoucí práce) ; Marx, Dániel (oponent)
Instance problému orientované Steinerovy sítě (zkracováno na DSN podle anglického názvu) je tvořena orientovaným grafem G s cenami hran a k tzv. "terminálními" páry vrcholů. Cílem je najít podgraf G s minimální cenou, ve kterém je každý terminální pár propojen cestou. Toto zobecňuje několik NP-těžkých problémů. Terminální páry indukují takzvaný "vzorový graf", orientovaný graf na podmnožině vrcholů G. V této práci se zabýváme problémem DSN omezeným na určité třídy vzorových grafů. Ví se, že optimum lze najít v FPT čase pro některé třídy, a že to není možné pro všechny ostatní třídy, za předpokladu že FPT ̸= W[1]. To vede na otázku, jak dobře lze ony těžké třídy aproximovat v FPT čase. Doká- žeme, že pro ně neexistuje FPT aproximační schéma na základě silnějšího předpokladu, Gap-ETH hypotézy. Poté ukážeme algoritmy s konstantním aproximačním faktorem pro speciální třídy vzorových grafů. 1
|
host ::
RSS.