Discrete Optimization via Continuous Relaxation
2017-09-11..2017-09-15
Berkeley, United States
[Optimization and Algorithm Design 2023, Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017), Semidefinite Optimization, Approximation and Applications 2014, Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms, ITCS 2022, Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015)]
who it's for
approximation algorithm researchers, combinatorial optimization researchers, integer programming researchers, submodular optimization researchers, graph algorithm researchers, scheduling researchers, statistical-computation researchers
topics
sum-of-squares to spectral tests; LP hierarchies for scheduling; simplex embedding for multiway cut; exponential-clock rounding and CKR; time-indexed LP scheduling; compact LPs for orienteering; LP rounding for poise; submodular maximization with knapsack; dependent rounding techniques; bimodular integer programming; constant-factor asymmetric TSP; directed connectivity polylog approximation
| title | author | length |
|---|---|---|
| The Power of Hierarchies for Detecting Hidden Structures | Prasad Raghavendra | 01h 07m |
Proves that degree-D sum-of-squares power to distinguish planted vs. null instances reduces to a concrete spectral test: build a low-degree matrix polynomial… | ||
| Simplex Transformations and Multiway Cut | Roy Schwartz | 33m |
Uses the LP simplex embedding for multiway cut and replaces coordinatewise distortions with global, order-based transformations with dependencies plus a… | ||
| LPs and Convex Programming Relaxations and Rounding for Stochastic Problems | Anupam Gupta | 32m |
Projects exponential decision trees down to small LP surrogate for decision tree variables (marginals) and rounds them back into policies; assumes independent… | ||
| Discrepancy and Approximation Algorithms | Sasho Nikolov | 01h 04m |
Shows that linear discrepancy (worst-case rounding error from fractional LP solutions) is bounded by hereditary discrepancy and that this yields concrete… | ||
| On Approximating the Covering Radius and Finding Dense Lattice Subspaces | Daniel Dadush | 32m |
Gives concrete claims: computes a near-optimal dense lattice subspace in single-exponential time (2^{O(n)}) and finds projection certificates that upper- and… | ||
| A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming | Rico Zenklusen | 32m |
Proves a strongly polynomial algorithm for integer programs whose constraint matrix has all minors in {−2,−1,0,1,2} (bimodular). Key steps: solve the LP… | ||
| Improved Approximation Algorithms for the TSP and S-t-path TSP | David Shmoys | 01h 01m |
Survey of concrete advances: metric TSP stays at 3/2 for tours while the S–T path gap drops from Hoogeveen’s 5/3 using a concrete algorithmic recipe: solve the… | ||
| A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem | László Végh | 01h 08m |
Claims a constant-factor algorithm for general Asymmetric TSP measured against the Held-Karp relaxation, replacing prior polylog bounds. Method: solve LP dual… | ||
| Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing | Chaitanya Swamy | 30m |
Presents compact polynomial-size LPs for rooted orienteering and regret-bounded vehicle routing, and an LP rounding that yields a 3-approximation LP rounding… | ||
| Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation... | Fabrizio Grandoni | 28m |
Claim: a quasi-polynomial-time algorithm achieves a polylogarithmic approximation for directed connectivity variants that require groups of terminals to reach… | ||
| Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations | Shi Li | 30m |
Uses a time-indexed LP with a rectangle view of job start times, then samples a rectangle per job and randomizes an offset (choice of a theta distribution) to… | ||
| LP Rounding for Poise | R. Ravi | 32m |
Gives an LP rounding algorithm that produces a spanning (or Steiner) tree whose sum of diameter and maximum degree (poise) is within O(log n) of the LP… | ||
| Submodular Optimization | Niv Buchbinder | 59m |
Maximizing submodular set functions under constraints uses concrete algorithms and tight ratios: greedy gives 1 - 1/e for monotone cardinality but fails for… | ||
| Submodular Unsplittable Flow on Trees | Anna Adamaszek | 29m |
Gives a concrete algorithmic pipeline that yields a K log n approximation for submodular unsplittable flow on trees: reduce to intersecting instances (losing a… | ||
| A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint | Alina Ene | 33m |
Claims a nearly-linear number of value queries (roughly N log^2 N) to get a 1 - 1/e - ε approximation for submodular maximization under a knapsack, improving… | ||
| Online Optimization, Smoothing, and Competitive Ratio | Maryam Fazel | 01h 01m |
Claims that competitive ratio for online resource allocation improves if the objective psi is optimally smoothed; derives a concrete scalar metric alpha… | ||
| The Non-Uniform k-Center Problem | Deeparnab Chakrabarty | 32m |
Classic k‑center stays 2‑approx, and the nonuniform version gets concrete results: an LP-to-firefighter reduction converts a fractional solution on the metric… | ||
| Beyond Worst Case Analysis in Approximation | Uri Feige | 57m |
Surveys five problems and gives concrete claims: Max‑3SAT is stuck at a 7/8 hardness threshold even for natural random formulas; Min‑Bisection and 3‑coloring… | ||
| Algorithms for Stable and Perturbation-resilient Problems | Kostya Makarychev | 32m |
Proves that gamma=2 perturbation resilience for k‑means and k‑median implies a center‑proximity property, shows each optimal cluster is a subtree of the… | ||
| Scheduling on Related Machines | Debmalya Panigrahi | 29m |
Claims a constant competitive algorithm for online scheduling on related machines for arbitrary l_q norms, using a new fractional relaxation with two terms (a… | ||
| Low Diameter Graph Decompositions and Approximating Unique Games | Lap-Chi Lau | 34m |
Proves a concrete pipeline: solve an LP with odd-cycle constraints, delete edges with x_e>1/2 (cost ≤2·LP), then run a low-diameter decomposition with Δ=1/4 so… | ||
| A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies | Thomas Rothvoß | 55m |
Claim: a 1+ε approximation for makespan on unit-length jobs with constant M, achieved by strengthening the time-indexed LP via the Sherali–Adams hierarchy… | ||
| LP Relaxations for Reordering Buffer Management | Yuval Rabani | 35m |
LPs model the output as fractional batches and the dual as Y and Z prices; rounding one natural LP doubles cost but needs a buffer of size about 2K, yielding… | ||
| A Survey of Dependent Rounding | Aravind Srinivasan | 58m |
Algorithms round fractional edge/node variables to 0/1 while preserving marginals and forcing per-constraint sums to the integer value, using a simple pairwise… | ||
| Finding Best LP Relaxations for Various Cut Problems | Euiwoong Lee | 26m |
Proposes an estimation algorithm that, for fixed demand graph H, enumerates unambiguous supergraph F choices and returns the minimum standard flow‑LP value… | ||
| Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration | Nisheeth Vishnoi | 34m |
Presents randomized algorithms that actually output sets for constrained subdeterminant maximization over regular matroids and partition matroids, using a… | ||
| Approximating the Permanent of Positive Semidefinite Matrices | Nima Anari | 29m |
Proves a deterministic algorithm that approximates the permanent of any positive semidefinite matrix to a simply exponential factor (≈ e^{γ+1}^n), using a… | ||
| Local Guarantees in Graph Cuts and Clustering | Moses Charikar | 28m |
Defines min-max variants of cuts and correlation clustering, gives an LP relaxation and a deterministic ball-growing rounding that picks a 1/7 ball then a 3/7… | ||
| nothing matches | ||