On a generalization of iterated and randomized rounding

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Uittreksel

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.

TaalEngels
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

Trefwoorden

    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). New York: Association for Computing Machinery, Inc. DOI: 10.1145/3313276.3316313
    Bansal, Nikhil. / On a generalization of iterated and randomized rounding. STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. redacteur / Moses Charikar ; Edith Cohen. New York : Association for Computing Machinery, Inc, 2019. blz. 1125-1135
    @inproceedings{b7df6b9551574223af14c03960bed18c,
    title = "On a generalization of iterated and randomized rounding",
    abstract = "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.",
    keywords = "Approximation algorithms, Dependent rounding, Iterating rounding, Randomized rounding",
    author = "Nikhil Bansal",
    year = "2019",
    month = "6",
    day = "23",
    doi = "10.1145/3313276.3316313",
    language = "English",
    pages = "1125--1135",
    editor = "Moses Charikar and Edith Cohen",
    booktitle = "STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing",
    publisher = "Association for Computing Machinery, Inc",
    address = "United States",

    }

    Bansal, N 2019, On a generalization of iterated and randomized rounding. in M Charikar & E Cohen (redactie), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, Inc, New York, blz. 1125-1135, Phoenix, Verenigde Staten van Amerika, 23/06/19. DOI: 10.1145/3313276.3316313

    On a generalization of iterated and randomized rounding. / Bansal, Nikhil.

    STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. redactie / Moses Charikar; Edith Cohen. New York : Association for Computing Machinery, Inc, 2019. blz. 1125-1135.

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    TY - GEN

    T1 - On a generalization of iterated and randomized rounding

    AU - Bansal,Nikhil

    PY - 2019/6/23

    Y1 - 2019/6/23

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

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

    KW - Approximation algorithms

    KW - Dependent rounding

    KW - Iterating rounding

    KW - Randomized rounding

    UR - http://www.scopus.com/inward/record.url?scp=85068742161&partnerID=8YFLogxK

    U2 - 10.1145/3313276.3316313

    DO - 10.1145/3313276.3316313

    M3 - Conference contribution

    SP - 1125

    EP - 1135

    BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

    PB - Association for Computing Machinery, Inc

    CY - New York

    ER -

    Bansal N. On a generalization of iterated and randomized rounding. In Charikar M, Cohen E, redacteurs, STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. New York: Association for Computing Machinery, Inc. 2019. blz. 1125-1135. Beschikbaar vanaf, DOI: 10.1145/3313276.3316313