Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Improved (In-)Approximability Bounds for d-Scattered Set
verfasst von : Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In the \(d\)-Scattered Set problem we are asked to select at least k vertices of a given graph, so that the distance between any pair is at least d. We study the problem’s (in-)approximability and offer improvements and extensions of known results for Independent Set, of which the problem is a generalization. Specifically, we show:
-
A lower bound of \(\Delta ^{\lfloor d/2\rfloor -\epsilon }\) on the approximation ratio of any polynomial-time algorithm for graphs of maximum degree \(\Delta \) and an improved upper bound of \(O(\Delta ^{\lfloor d/2\rfloor })\) on the approximation ratio of any greedy scheme for this problem.
-
A polynomial-time \(2\sqrt{n}\)-approximation for bipartite graphs and even values of d, that matches the known lower bound by considering the only remaining case.
-
A lower bound on the complexity of any \(\rho \)-approximation algorithm of (roughly) \(2^{\frac{n^{1-\epsilon }}{\rho d}}\) for even d and \(2^{\frac{n^{1-\epsilon }}{\rho (d+\rho )}}\) for odd d (under the randomized ETH), complemented by \(\rho \)-approximation algorithms of running times that (almost) match these bounds.