LP-based robust algorithms for noisy minor-free and bounded treewidth graphs
Bansal, N Nikhil, Daniel Reichman, Umboh, SW · TU/e Research Portal · 2017
We give a general approach for solving optimization problems on noisy minor free and bounded treewidth graphs, where a fraction of edges are adversarially corrupted. The noisy setting was first considered by Magen and Moharrami and they gave a (1 + ∊)-estimation algorithm for the independent set problem. Later, Chan and Har-Peled designed a local search algorithm that finds a (1 + ∊)-approximate independent set. However, nothing was known regarding other problems in the noisy setting. Our main contribution is a general LP-based framework that yields (1 + ∊)-approximation algorithms for noisy MAX-k-CSPs.