{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/106153"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/106153","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fast approximations for combinatorial optimization via multiplicative weight updates","abstract":"\"We develop fast approximations for several LP relaxations that arise in discrete and combinatorial optimization. New results include improved running times for explicit mixed packing and covering problems, nearly linear time approximations for tree packings, nearly linear time approximations for the Held Karp bound (leading to a significantly faster $(3/2 + \\epsilon)$-approximation for metric TSP), faster approximations for covering LPs with knapsack covering constraints (the bottleneck for covering integer programs), and nearly linear time $(2+\\epsilon)$-approximations for $k$-cut via the LP. Along the way we develop new techniques for the MWU framework and put forth two frameworks, \"\"lazy MWU\"\" for deterministic algorithms and \"\"randomized MWU\"\" for randomized algorithms, that algorithm designers can use to obtain nearly linear running times for their own problems of interest. This thesis has been organized as a user friendly guide, where we include basic background and analysis of the MWU framework, establish clean interfaces for the two frameworks, and use the applications as examples of the frameworks.\"","abstract_html":"&quot;We develop fast approximations for several LP relaxations that arise in discrete and combinatorial optimization. New results include improved running times for explicit mixed packing and covering problems, nearly linear time approximations for tree packings, nearly linear time approximations for the Held Karp bound (leading to a significantly faster <span class=\"etd-inline-math\">(3/2 + &epsilon;)</span>-approximation for metric TSP), faster approximations for covering LPs with knapsack covering constraints (the bottleneck for covering integer programs), and nearly linear time <span class=\"etd-inline-math\">(2+&epsilon;)</span>-approximations for $k$-cut via the LP. Along the way we develop new techniques for the MWU framework and put forth two frameworks, &quot;&quot;lazy MWU&quot;&quot; for deterministic algorithms and &quot;&quot;randomized MWU&quot;&quot; for randomized algorithms, that algorithm designers can use to obtain nearly linear running times for their own problems of interest. This thesis has been organized as a user friendly guide, where we include basic background and analysis of the MWU framework, establish clean interfaces for the two frameworks, and use the applications as examples of the frameworks.&quot;","abstract_has_math":true,"creators":["Quanrud, Kent"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chekuri, Chandra","Har-Peled, Sariel","Erickson, Jeff","Young, Neal E","Blum, Avrim"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-03-02T21:57:57Z","date_published":"2020-03-02T21:57:57Z","updated_at":"2026-07-22T22:24:45Z","subjects":["Approximation algorithms","Linear programming","Combinatorial optimization","fast approximations","traveling salesman problem"],"languages":["en"],"rights":["Copyright 2019 Kent Quanrud"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/106153","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chekuri, Chandra","Har-Peled, Sariel","Erickson, Jeff","Young, Neal E","Blum, Avrim"]},{"key":"dc:creator","label":"Author","values":["Quanrud, Kent"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-03-02T21:57:57Z","2019-09-30","2019-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Approximation algorithms","Linear programming","Combinatorial optimization","fast approximations","traveling salesman problem"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Kent Quanrud"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/106153"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"We develop fast approximations for several LP relaxations that arise in discrete and combinatorial optimization. New results include improved running times for explicit mixed packing and covering problems, nearly linear time approximations for tree packings, nearly linear time approximations for the Held Karp bound (leading to a significantly faster $(3/2 + \\epsilon)$-approximation for metric TSP), faster approximations for covering LPs with knapsack covering constraints (the bottleneck for covering integer programs), and nearly linear time $(2+\\epsilon)$-approximations for $k$-cut via the LP. Along the way we develop new techniques for the MWU framework and put forth two frameworks, \"\"lazy MWU\"\" for deterministic algorithms and \"\"randomized MWU\"\" for randomized algorithms, that algorithm designers can use to obtain nearly linear running times for their own problems of interest. This thesis has been organized as a user friendly guide, where we include basic background and analysis of the MWU framework, establish clean interfaces for the two frameworks, and use the applications as examples of the frameworks.\"","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, Kent Quanrud, accepted the attached license on 2019-09-13 at 13:53.","The student, Kent Quanrud, submitted this Dissertation for approval on 2019-09-13 at 14:01.","This Dissertation was approved for publication on 2019-09-30 at 14:15.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14454 on 2020-02-28 at 17:11:34","Made available in DSpace on 2020-03-02T21:57:57Z (GMT). No. of bitstreams: 2 QUANRUD-DISSERTATION-2019.pdf: 1550941 bytes, checksum: dfd1b1852a3c69ae90d19a77e49a6f1b (MD5) LICENSE.txt: 4209 bytes, checksum: eac8340036098075affd7456712966f8 (MD5) Previous issue date: 2019-09-30"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Fast approximations for combinatorial optimization via multiplicative weight updates"]}]}],"canonical_facts":{"dc:contributor":["Chekuri, Chandra","Har-Peled, Sariel","Erickson, Jeff","Young, Neal E","Blum, Avrim"],"dc:creator":["Quanrud, Kent"],"dc:date":["2020-03-02T21:57:57Z","2019-09-30","2019-12"],"dc:description":["\"We develop fast approximations for several LP relaxations that arise in discrete and combinatorial optimization. New results include improved running times for explicit mixed packing and covering problems, nearly linear time approximations for tree packings, nearly linear time approximations for the Held Karp bound (leading to a significantly faster $(3/2 + \\epsilon)$-approximation for metric TSP), faster approximations for covering LPs with knapsack covering constraints (the bottleneck for covering integer programs), and nearly linear time $(2+\\epsilon)$-approximations for $k$-cut via the LP. Along the way we develop new techniques for the MWU framework and put forth two frameworks, \"\"lazy MWU\"\" for deterministic algorithms and \"\"randomized MWU\"\" for randomized algorithms, that algorithm designers can use to obtain nearly linear running times for their own problems of interest. This thesis has been organized as a user friendly guide, where we include basic background and analysis of the MWU framework, establish clean interfaces for the two frameworks, and use the applications as examples of the frameworks.\"","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-02-28 without embargo terms","The student, Kent Quanrud, accepted the attached license on 2019-09-13 at 13:53.","The student, Kent Quanrud, submitted this Dissertation for approval on 2019-09-13 at 14:01.","This Dissertation was approved for publication on 2019-09-30 at 14:15.","DSpace SAF Submission Ingestion Package generated from Vireo submission #14454 on 2020-02-28 at 17:11:34","Made available in DSpace on 2020-03-02T21:57:57Z (GMT). No. of bitstreams: 2 QUANRUD-DISSERTATION-2019.pdf: 1550941 bytes, checksum: dfd1b1852a3c69ae90d19a77e49a6f1b (MD5) LICENSE.txt: 4209 bytes, checksum: eac8340036098075affd7456712966f8 (MD5) Previous issue date: 2019-09-30"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/106153"],"dc:language":["en"],"dc:rights":["Copyright 2019 Kent Quanrud"],"dc:subject":["Approximation algorithms","Linear programming","Combinatorial optimization","fast approximations","traveling salesman problem"],"dc:title":["Fast approximations for combinatorial optimization via multiplicative weight updates"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:45Z"}