Discrete Optimization via Continuous Relaxation

source: Simons Institute        2017年9月11日
Much of the progress in solving discrete optimization problems, especially in terms of approximation algorithms, has come from designing novel continuous relaxations. The primary tools in this area are linear programming and semidefinite programming. Other forms of relaxations have also been developed, such as multilinear relaxation for submodular optimization. In this workshop, we explore the state-of-the-art techniques for performing discrete optimization based on continuous relaxations of the underlying problem, as well as our current understanding of the limitations of this kind of approach. We focus on LP/SDP relaxations and techniques for rounding their solutions, as well as methods for submodular optimization, both in the offline and online setting. We also investigate the limits of such relaxations and hardness of approximation results.
For more information, please visit: https://simons.berkeley.edu/workshops...
These presentations were supported in part by an award from the Simons Foundation.

1 1:07:15 The Power of Hierarchies for Detecting Hidden Structures
2 33:25 Simplex Transformations and Multiway Cut
3 31:45 LPs and Convex Programming Relaxations and Rounding for Stochastic Problems
4 1:03:56 Discrepancy and Approximation Algorithms
5 31:42 On Approximating the Covering Radius and Finding Dense Lattice Subspaces
6 31:35 A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming
7 1:01:27 Improved Approximation Algorithms for the TSP and S-t-path TSP
8 1:07:59 A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
9 30:12 Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing
10 28:28 Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation...
11 30:26 Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations
12 32:19 LP Rounding for Poise
13 59:18 Submodular Optimization
14 29:26 Submodular Unsplittable Flow on Trees
15 33:03 A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
16 1:00:56 Online Optimization, Smoothing, and Competitive Ratio
17 32:13 The Non-Uniform k-Center Problem
18 56:56 Beyond Worst Case Analysis in Approximation
19 32:15 Algorithms for Stable and Perturbation-resilient Problems
20 29:25 Scheduling on Related Machines
21 34:10 Low Diameter Graph Decompositions and Approximating Unique Games
22 54:30 A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
23 34:39 LP Relaxations for Reordering Buffer Management
24 58:13 A Survey of Dependent Rounding
25 26:10 Finding Best LP Relaxations for Various Cut Problems
26 34:27 Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration
27 29:10 Approximating the Permanent of Positive Semidefinite Matrices
28 28:11 Local Guarantees in Graph Cuts and Clustering