University of Illinois Urbana-Champaign

Fast approximations for combinatorial optimization via multiplicative weight updates

Quanrud, Kent

Permalink

https://hdl.handle.net/2142/106153

Description

Title
Fast approximations for combinatorial optimization via multiplicative weight updates
Author(s)
Quanrud, Kent
Issue Date
2019-09-30
Director of Research (if dissertation) or Advisor (if thesis)
Chekuri, Chandra
Doctoral Committee Chair(s)
Chekuri, Chandra
Committee Member(s)
  • Har-Peled, Sariel
  • Erickson, Jeff
  • Young, Neal E
  • Blum, Avrim
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • Approximation algorithms
  • Linear programming
  • Combinatorial optimization
  • fast approximations
  • traveling salesman problem
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."
Graduation Semester
2019-12
Type of Resource
text
Permalink
http://hdl.handle.net/2142/106153
Copyright and License Information
Copyright 2019 Kent Quanrud

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Dept. of Computer Science