TL;DR
This paper proves that the matching problem, despite being solvable in polynomial time, cannot be approximated within a factor of $1 - \epsilon/n$ using a linear program (LP) with a polynomial number of inequalities. This establishes that matching is the first problem in P that lacks a "fully polynomial-size LP relaxation scheme," a significant theoretical finding with implications for understanding the limits of LP expressiveness.
What Problem Does This Paper Address?
The paper tackles a fundamental question in theoretical computer science: how efficiently can combinatorial optimization problems be represented and solved using linear programming (LP)? Specifically, it focuses on the "extension complexity" of polytopes, which measures the size of the smallest LP formulation (number of inequalities) needed to represent a given polytope. While many problems can be solved efficiently, their LP formulations might require an exponential number of inequalities. This is particularly intriguing for problems like matching, which are in P.
Previous work by Rothvoß showed that the matching polytope itself has exponential extension complexity. This paper extends this by investigating the approximability of the matching problem using LPs. The core question is whether we can get good approximations (e.g., within a factor of $1-\epsilon$) using LPs that are "small" (polynomial in the input size and $1/\epsilon$). The paper addresses the gap between existing polynomial-time solvable problems and the potential limitations of their LP representations, particularly concerning approximation.
Methods
The paper employs an information-theoretic approach to establish lower bounds on the size of LP formulations. This method builds upon the framework developed in prior work by Braun and Pokutta. The key technique involves analyzing the "common information" between random variables, a concept from information theory introduced by Wyner.
The authors connect the extension complexity of a polytope to the nonnegative rank of its slack matrices. They then use common information to derive lower bounds on this nonnegative rank. A crucial aspect of their method is a "direct sum" argument, which breaks down the problem into smaller, independent subproblems. This allows them to amplify the complexity of these small chunks to obtain an exponential lower bound for the overall problem. The proof strategy involves:
- Reduction to a local case: The problem is simplified by considering a specific structure of vertices and matchings, effectively isolating a smaller, representative subproblem.
- Information-theoretic analysis: Pinsker's inequality and the concept of common information are used to bound the mutual information related to the problem's structure.
- Bounding "bad" pairs: The analysis focuses on identifying and quantifying "bad" pairs of parameters that lead to significant differences in probability distributions, which in turn contribute to the lower bound on mutual information.
Datasets
Not discussed in the paper. The paper deals with theoretical problems and does not use empirical datasets.
Key Insights and Ideas
- Matching is fundamentally hard for LP approximation: Even though matching can be solved exactly in polynomial time, approximating it with an LP requires an exponential number of inequalities for guarantees better than $1 - \Theta(1/n)$. This is a sharp separation from existing polynomial-size approximations.
- Information theory as a powerful tool for LP complexity: The paper demonstrates the effectiveness of using information-theoretic quantities like common information to prove lower bounds on the size of LP formulations, offering a new perspective beyond traditional combinatorial methods.
- Direct sum structure as a source of hardness: The exponential complexity of the matching problem (and similar problems like the correlation polytope) stems from an inherent "direct sum" structure, where the problem can be decomposed into many similar, independent subproblems.
- FPSRS vs. PSRS distinction: The paper highlights the difference between a "fully polynomial-size LP relaxation scheme" (FPSRS, analogous to FPTAS) and a "polynomial-size LP relaxation scheme" (PSRS, analogous to PTAS). Matching admits the latter but not the former.
Key Results
- No Fully Polynomial-Size LP Relaxation Scheme (FPSRS) for Matching: The paper proves that for any fixed $\epsilon > 0$, approximating the matching problem within a factor of $1 - \epsilon/n$ requires an LP formulation with an exponential number of inequalities. This means matching does not admit an FPSRS.
- Exponential Lower Bound on Formulation Complexity: The formulation complexity (size of LP formulation) of the matching problem is shown to be $\Omega(2^{n/\log n})$ (or similar exponential form, specifically $\Omega(2^{n})$ in Theorem 3.1).
- Generalization of Rothvoß's Result: The work extends Rothvoß's finding about the exponential extension complexity of the matching polytope to the realm of approximation, showing that even approximate solutions demand large LP formulations.
Limitations and Future Work
- Semidefinite Programming (SDP) Formulations: The paper notes that while their information-theoretic framework is powerful, it's an open question whether it can be adapted to prove similar exponential lower bounds for semidefinite programming relaxations of the matching problem. This is a direction for future research.
- Generalizability: The authors believe their information-theoretic approach could be extended to prove similar inapproximability results for other combinatorial problems.
- Refining the Direct Sum Structure: The direct sum structure used for matching is a simplified variant of Rothvoß's, and further exploration of this structure might yield deeper insights.
Summary updated