2009 | OriginalPaper | Buchkapitel
Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
verfasst von : Avner Magen, Mohammad Moharrami
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
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
This work provides a Linear Programming-based Polynomial Time Approximation Scheme (PTAS) for two classical NP-hard problems on graphs when the input graph is guaranteed to be planar, or more generally Minor Free. The algorithm applies a sufficiently large number (some function of 1/
ε
when 1 +
ε
approximation is required) of rounds of the so-called Sherali-Adams Lift-and-Project system. needed to obtain a (1 +
ε
)-approximation, where
f
is some function that depends only on the graph that should be avoided as a minor. The problem we discuss are the well-studied problems, the
and
problems. An curious fact we expose is that in the world of minor-free graph, the
is harder in some sense than the
.
Our main result shows how to get a PTAS for
in the more general “noisy setting” in which input graphs are not assumed to be planar/minor-free, but only close to being so. In this setting we bound integrality gaps by 1 +
ε
, which in turn provides a 1 +
ε
approximation of the optimum value; however we don’t know how to actually find a solution with this approximation guarantee. While there are known combinatorial algorithms for the non-noisy setting of the above graph problems, we know of no previous approximation algorithms in the noisy setting. Further, we give evidence that current combinatorial techniques will fail to generalize to this noisy setting.