LP-based robust algorithms for noisy minor-free and bounded treewidth graphs

N. Bansal; D. Reichman; S.W. Umboh

doi:10.1137/1.9781611974782.128

LP-based robust algorithms for noisy minor-free and bounded treewidth graphs

N. Bansal
, D. Reichman
, S.W. Umboh

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

11 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
Editors	Philip N. Klein
Publisher	Society for Industrial and Applied Mathematics (SIAM)
Pages	1964-1979
Number of pages	16
ISBN (Electronic)	978-1-61197-478-2
DOIs	https://doi.org/10.1137/1.9781611974782.128
Publication status	Published - 2017
Event	28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 Conference number: 28

Conference

Conference	28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
Abbreviated title	SODA 2017
Country/Territory	Spain
City	Barcelona
Period	16/01/17 → 19/01/17

Access to Document

10.1137/1.9781611974782.128

Cite this

@inproceedings{ec0006d2919940bbbe3a0f5f87acb1fa,

title = "LP-based robust algorithms for noisy minor-free and bounded treewidth graphs",

abstract = "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.",

author = "N. Bansal and D. Reichman and S.W. Umboh",

year = "2017",

doi = "10.1137/1.9781611974782.128",

language = "English",

pages = "1964--1979",

editor = "Klein, \{Philip N.\}",

booktitle = "Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

address = "United States",

note = "28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), SODA 2017 ; Conference date: 16-01-2017 Through 19-01-2017",

}

Bansal, N, Reichman, D & Umboh, SW 2017, LP-based robust algorithms for noisy minor-free and bounded treewidth graphs. in PN Klein (ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics (SIAM), pp. 1964-1979, 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Barcelona, Spain, 16/01/17. https://doi.org/10.1137/1.9781611974782.128

LP-based robust algorithms for noisy minor-free and bounded treewidth graphs. / Bansal, N.; Reichman, D.; Umboh, S.W.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Philip N. Klein. Society for Industrial and Applied Mathematics (SIAM), 2017. p. 1964-1979.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - LP-based robust algorithms for noisy minor-free and bounded treewidth graphs

AU - Bansal, N.

AU - Reichman, D.

AU - Umboh, S.W.

N1 - Conference code: 28

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85016226856

U2 - 10.1137/1.9781611974782.128

DO - 10.1137/1.9781611974782.128

M3 - Conference contribution

SP - 1964

EP - 1979

BT - Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Klein, Philip N.

PB - Society for Industrial and Applied Mathematics (SIAM)

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

Y2 - 16 January 2017 through 19 January 2017

ER -

LP-based robust algorithms for noisy minor-free and bounded treewidth graphs

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this