Polyhedral techniques in combinatorial optimization: matchings and tours

Ola SvenssonEMS 2023 · DOI · OpenAlex

TL;DR

This paper overviews how "polyhedral techniques"—the study of the geometric structure of linear programming relaxations—have recently cracked two of the toughest nuts in combinatorial optimization. It highlights the path toward deterministic parallel algorithms for perfect matchings and the breakthrough discovery of the first constant-factor approximation algorithm for the Asymmetric Traveling Salesman Problem (ATSP).

What Problem Does This Paper Address?

The paper tackles the gap between what we know is possible and what we can actually prove for two foundational problems: Matchings and the Traveling Salesman Problem (TSP).

  1. Perfect Matchings: While we’ve had polynomial-time algorithms since 1965, we still lack a truly efficient deterministic parallel algorithm. Current parallel methods rely on randomization (the "Isolation Lemma"), and "derandomizing" these remains a major challenge in complexity theory.
  2. Asymmetric TSP (ATSP): In the symmetric version of TSP (where the distance from A to B is the same as B to A), we’ve had good approximations for decades. However, the asymmetric version—where one-way streets or wind resistance make distances unequal—was stuck with approximation factors that grew with the number of cities ($\log n$). Researchers spent decades searching for a "constant-factor" algorithm that stays accurate regardless of the map's size.

Methods

The author argues that the "secret sauce" for recent progress in both fields is a deep dive into polyhedral techniques. This involves looking at the convex hull of all possible solutions and using Linear Programming (LP) relaxations—even those with an exponential number of constraints—to find hidden structures.

  • For Matchings: The paper describes a framework that builds weight functions in rounds. By using "circulations" and "girth" (the length of the shortest cycle) as progress measures, the algorithm iteratively narrows down the set of possible matchings until only one unique minimum-weight matching remains (isolating it).
  • For ATSP: The method uses a series of reductions to simplify general distances into "node-weighted" or "laminarly-weighted" instances. It relies heavily on the Held-Karp relaxation, an LP that enforces connectivity across every possible cut in the graph.

Datasets

As this is a theoretical overview paper focused on algorithmic proofs and complexity, it does not use empirical datasets or benchmarks. The "evaluation" is mathematical proof of the algorithms' performance bounds.

Key Insights and Ideas

  • The Power of Laminarity: A unifying theme is the "laminar structure" of extreme points. In both matching and ATSP, the sets of tight constraints in the optimal LP solution form a laminar family—meaning any two sets are either nested or completely disjoint. This tree-like structure allows researchers to use divide-and-conquer strategies on problems that otherwise look like a tangled mess.
  • Girth as a Progress Measure: For bipartite matchings, the paper shows that you can "double the girth" of the graph in each round. If you can ensure that all "short" cycles have a non-zero weight, you can eventually force the graph to have no cycles at all, leaving a unique matching.
  • Thin Spanning Trees: The paper discusses the "thinness" property—finding a spanning tree that doesn't cross any cut in the graph too many times relative to the LP solution. This concept was a bridge that eventually led to the constant-factor breakthrough for ATSP.

Key Results

  • Deterministic Parallel Matchings: The paper details the first "quasi-NC" algorithm for bipartite matching (meaning it’s almost perfectly parallelizable) and its extension to general graphs using $O(\log^2 n)$ weight functions.
  • ATSP Breakthrough: After decades of stagnation, the author (along with collaborators) achieved the first constant-factor approximation for ATSP. While the initial proof was complex, subsequent refinements have brought the approximation guarantee down to a factor of 22.

Limitations and Future Work

  • The "Quasi" Problem: For matchings, the current deterministic algorithms are "quasi-polynomial." Reaching a true "NC" algorithm (fully polynomial parallel time) remains an open "holy grail."
  • Variant Challenges: Problems like "Exact Matching" (finding a matching with a specific total weight) still lack efficient deterministic algorithms and likely require entirely new polyhedral insights.
  • Closing the Gap for ATSP: While a constant factor of 22 is a massive theoretical win, it is still far from the conjectured "integrality gap" of 2. The search continues for a simpler, more efficient constant-factor algorithm that could be used in practice.
  • The Thin-Tree Conjecture: A major open question remains: does every ATSP instance contain a $O(1)$-thin tree? Proving this would provide a much more elegant path to approximating the problem.

Summary updated

Abstract

We overview recent progress on two of the most classical problems in combinatorial optimization, namely the matching problem and the traveling salesman problem. We focus on deterministic parallel algorithms for the perfect matching problem and the first constant-factor approximation algorithm for the asymmetric traveling salesman problem. While these questions pose seemingly different challenges, recent progress has been achieved using similar polyhedral techniques. In particular, for both problems, we use linear programming formulations, even exponential-sized ones, to extract structure from problem instances to guide the design of algorithms.
BibTeX
@inproceedings{svensson2023polyhedral,
  author = {Ola Svensson},
  title = {{Polyhedral techniques in combinatorial optimization: matchings and tours}},
  booktitle = {EMS},
  year = {2023},
  doi = {10.4171/icm2022/127},
}

Loading related content...

Figure