On a generalization of iterated and randomized rounding

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

We give a general method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, we show that whenever iterated rounding can be applied to a problem with some slack, there is a randomized procedure that returns an integral solution that satisfies the guarantees of iterated rounding and also has concentration properties. We use this to give new results for several classic problems where iterated rounding has been useful.

Originele taal-2Engels
TitelSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
RedacteurenMoses Charikar, Edith Cohen
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's1125-1135
Aantal pagina's11
ISBN van elektronische versie978-1-4503-6705-9
DOI's
StatusGepubliceerd - 23 jun 2019
Evenement51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, Verenigde Staten van Amerika
Duur: 23 jun 201926 jun 2019

Congres

Congres51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
LandVerenigde Staten van Amerika
StadPhoenix
Periode23/06/1926/06/19

Citeer dit

Bansal, N. (2019). On a generalization of iterated and randomized rounding. In M. Charikar, & E. Cohen (editors), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (blz. 1125-1135). Association for Computing Machinery, Inc. https://doi.org/10.1145/3313276.3316313