Approximation-friendly discrepancy rounding

Nikhil Bansal; Viswanath Nagarajan

doi:10.1007/978-3-319-44479-6_4

Approximation-friendly discrepancy rounding

Nikhil Bansal, Viswanath Nagarajan

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

2 Citations (Scopus)

Abstract

Rounding linear programs using techniques from discrepancy is a recent approach that has been very successful in certain settings. However this method also has some limitationswhen compared to approaches such as randomized and iterative rounding.We provide an extension of the discrepancy-based rounding algorithmdue to Lovett-Meka that (i) combines the advantages of both randomized and iterated rounding, (ii) makes it applicable to settings with more general combinatorial structure such as matroids. As applications of this approach, we obtain new results for various classical problems such as linear system rounding, degree-bounded matroid basis and low congestion routing.

Original language	English
Title of host publication	A Journey Through Discrete Mathematics
Subtitle of host publication	A Tribute to Jiri Matousek
Editors	M. Loebl, R. Thomas, J. Nešetřil
Place of Publication	Dordrecht
Publisher	Springer
Pages	89-114
Number of pages	26
ISBN (Electronic)	978-3-319-44479-6
ISBN (Print)	978-3-319-44478-9
DOIs	https://doi.org/10.1007/978-3-319-44479-6_4
Publication status	Published - 1 Jan 2017

Access to Document

10.1007/978-3-319-44479-6_4

Cite this

@inbook{09b5185b3a894e0298437c5790a3406b,

title = "Approximation-friendly discrepancy rounding",

abstract = "Rounding linear programs using techniques from discrepancy is a recent approach that has been very successful in certain settings. However this method also has some limitationswhen compared to approaches such as randomized and iterative rounding.We provide an extension of the discrepancy-based rounding algorithmdue to Lovett-Meka that (i) combines the advantages of both randomized and iterated rounding, (ii) makes it applicable to settings with more general combinatorial structure such as matroids. As applications of this approach, we obtain new results for various classical problems such as linear system rounding, degree-bounded matroid basis and low congestion routing.",

author = "Nikhil Bansal and Viswanath Nagarajan",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/978-3-319-44479-6\_4",

language = "English",

isbn = "978-3-319-44478-9",

pages = "89--114",

editor = "M. Loebl and R. Thomas and J. Ne{\v s}et{\v r}il",

booktitle = "A Journey Through Discrete Mathematics",

publisher = "Springer",

address = "Germany",

}

TY - CHAP

T1 - Approximation-friendly discrepancy rounding

AU - Bansal, Nikhil

AU - Nagarajan, Viswanath

PY - 2017/1/1

Y1 - 2017/1/1

N2 - Rounding linear programs using techniques from discrepancy is a recent approach that has been very successful in certain settings. However this method also has some limitationswhen compared to approaches such as randomized and iterative rounding.We provide an extension of the discrepancy-based rounding algorithmdue to Lovett-Meka that (i) combines the advantages of both randomized and iterated rounding, (ii) makes it applicable to settings with more general combinatorial structure such as matroids. As applications of this approach, we obtain new results for various classical problems such as linear system rounding, degree-bounded matroid basis and low congestion routing.

AB - Rounding linear programs using techniques from discrepancy is a recent approach that has been very successful in certain settings. However this method also has some limitationswhen compared to approaches such as randomized and iterative rounding.We provide an extension of the discrepancy-based rounding algorithmdue to Lovett-Meka that (i) combines the advantages of both randomized and iterated rounding, (ii) makes it applicable to settings with more general combinatorial structure such as matroids. As applications of this approach, we obtain new results for various classical problems such as linear system rounding, degree-bounded matroid basis and low congestion routing.

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

U2 - 10.1007/978-3-319-44479-6_4

DO - 10.1007/978-3-319-44479-6_4

M3 - Chapter

AN - SCOPUS:85042444639

SN - 978-3-319-44478-9

SP - 89

EP - 114

BT - A Journey Through Discrete Mathematics

A2 - Loebl, M.

A2 - Thomas, R.

A2 - Nešetřil, J.

PB - Springer

CY - Dordrecht

ER -

Approximation-friendly discrepancy rounding

Abstract

Access to Document

Other files and links

Fingerprint

Cite this