Approximation-Friendly Discrepancy Rounding

Nikhil Bansal () and Viswanath Nagarajan
Additional contact information
Nikhil Bansal: Eindhoven University of Technology, Department of Mathematics and Computer Science
Viswanath Nagarajan: University of Michigan, Department of Industrial and Operations Engineering

A chapter in A Journey Through Discrete Mathematics, 2017, pp 89-114 from Springer

Abstract: 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 limitations when compared to approaches such as randomized and iterative rounding. We provide an extension of the discrepancy-based rounding algorithm due 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.

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-44479-6_4

Ordering information: This item can be ordered from
http://www.springer.com/9783319444796

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

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().