PaperlayerView exact revision on arXiv

Source-linked AI summary

A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution

Michel X. Goemans, Yuchong Pan

arXiv:2609.17932v1cs.DScs.DMmath.CO

TL;DR

Demand Matching generalizes knapsack and b-matching, and the paper addresses the lack of an approximation ratio strictly better than 3 for the problem. The algorithms use a strengthened knapsack-intersection LP and contention resolution for integral knapsack polytopes. The paper gives a randomized (2 + ε)-approximation for bipartite graphs and, to the authors’ knowledge, the first approximation ratio strictly below 3 for Demand Matching.

  • Problem

    Demand Matching generalizes knapsack and b-matching, and the paper addresses the lack of an approximation ratio strictly better than 3 for the problem.

    Source: §1 · p. 2

  • Method

    The algorithms use a strengthened knapsack-intersection LP and contention resolution for integral knapsack polytopes.

    Source: §1 · p. 2, §1.1 · p. 4

  • Results

    The paper gives a randomized (2 + ε)-approximation for bipartite graphs and, to the authors’ knowledge, the first approximation ratio strictly below 3 for Demand Matching.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For every q ∈ [0, 1], the integral knapsack polytope admits a (q, 1/(1+q))-balanced contention resolution scheme.

    Source: §1.1 · p. 4

    Further improving the approximation ratios and determining the exact integrality gaps of the knapsack intersection LP remain open questions.

    Source: §5 · p. 20

Abstract

from arXiv · show

The demand matching problem generalizes both the knapsack problem and the $b$-matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has a capacity. The goal is to find a maximum weight subset of edges such that, at each vertex, the total demand of the incident selected edges does not exceed the vertex capacity. Parekh [IPCO 2011] proved that, if each edge is individually feasible, the natural LP relaxation for demand matching has integrality gap at most $3$, yielding a $3$-approximation algorithm. This bound is tight for the natural LP relaxation, matching the lower bound of Shepherd and Vetta [Math. Oper. Res. 2007]. We present a randomized $(3/2 + \sqrt{2} + \varepsilon) \approx (2.914 + \varepsilon)$-approximation algorithm for the demand matching problem for every $\varepsilon > 0$, giving the first approximation ratio strictly better than $3$. For bipartite graphs, we obtain a randomized $(2 + \varepsilon)$-approximation algorithm for every $\varepsilon > 0$. Both algorithms run in time polynomial in $1/\varepsilon$ and the input length. Our algorithms use a strengthened LP relaxation based on intersecting the integral knapsack polytopes associated with the vertices, together with a multiple-choice generalization. As a key ingredient, we prove the existence of a $(q, 1/(1+q))$-balanced contention resolution scheme for the integral knapsack polytope for every $q \in [0, 1]$, which may be of independent interest. The balance guarantee $1/(1+q)$ is tight in the worst case over all knapsack instances.

1 Introduction

Demand Matching seeks a maximum-weight feasible edge set, generalizes b-matching and knapsack, and is NP-hard. The paper presents the first approximation ratio strictly below 3 and a (2 + ε)-approximation for bipartite graphs.

1 Introduction

  • Demand Matching generalizes maximum-weight b-matching in the unit-demand case and 0-1 knapsack on a star, making the problem NP-hard.The objective is to maximize the weight of selected edges while respecting each vertex’s capacity.Source: §1 · pp. 1–2
  • Without the no-bottleneck assumption, the natural LP relaxation has an unbounded integrality gap; Shepherd and Vetta also showed MAXSNP-hardness in the cardinality case.The no-bottleneck assumption requires each edge demand not to exceed either endpoint’s capacity.Source: §1 · p. 2
  • The paper gives a randomized (2 + ε)-approximation for bipartite graphs and, to the authors’ knowledge, the first approximation ratio strictly below 3 for Demand Matching.The guarantees use a strengthened LP relaxation rather than the natural LP relaxation.Source: §1 · p. 2

1.2 Organization of This Paper

  • For multigraphs, parallel edges can be correlated, so the paper uses bundling, approximate Pareto families, and multiple-choice sampling; section 4 extends the rounding algorithms.The paper’s organization assigns the knapsack scheme to section 2, simple graphs to section 3, multigraphs to section 4, and concluding questions to section 5.Source: §1.1 · p. 3, §1.2 · p. 6

1.1 Overview of the Algorithms

  • The knapsack intersection LP strengthens the natural relaxation by requiring each vertex’s incident-edge vector to belong to its integral knapsack polytope.It is the first level of the knapsack intersection hierarchy, which strengthens packing relaxations using integer hulls of constraint subsystems.Source: §1.1 · p. 3
  • For every q in [0, 1], the integral knapsack polytope admits a (q, 1/(1 + q))-balanced contention resolution scheme, and this guarantee is worst-case tight.The scheme is a key ingredient in the paper’s simple-graph rounding approach and may be of independent interest.Source: §1.1 · pp. 3–4
  • For simple bipartite graphs, independent source proposals followed by capacity-feasible sink selections yield an integrality gap of at most 2 for the knapsack intersection LP.Each sink’s proposed edges are independently sampled, allowing the knapsack contention-resolution guarantee to be applied.Source: §1.1 · p. 5
  • For general simple graphs, independently labeling vertices as sources or sinks enables rounding with a parameterized integrality-gap bound of (1 + q)/(2q(1 − q)).At a sink, each incident edge is sampled with probability qx_e before a feasible subset is selected.Source: §1.1 · pp. 5–6

2 CR Scheme for the Integral Knapsack Polytope

The section proves a balanced contention-resolution guarantee for the integral knapsack polytope by comparing sampled knapsack value with feasible sets represented by fractional marginals. Its proof uses deletion sensitivity to bound the loss from inserting a feasible set into the sample.

Theorem 1.2

  • E[r(R, B)] ≥ q/(1 + q) · w^T x for x in the integral knapsack polytope when R is sampled as R(qx).Here r(R, B) is the maximum weight of a capacity-feasible subset of R.Source: §2 · p. 6

Deletion sensitivity

  • Deletion sensitivity measures the maximum decrease in optimal knapsack value, over capacities up to ℓ, caused by deleting an item.Taking the maximum over capacities ensures the deletion-monotonicity property used in the proof.Source: §2 · pp. 6–7
  • Deletion sensitivity does not decrease when other items are removed, and the total sensitivity of a set is at most its optimal knapsack value.These properties bound the total increase in value when a feasible set is inserted into the sample.Source: §2 · pp. 6–7

Proof of Theorem 1.2

  • The proof inserts items of a feasible set into the sampled set one at a time, then averages the resulting value comparison over feasible sets and samples.The feasible set is drawn from a distribution whose marginals are x.Source: §2 · pp. 6, 8

3 Rounding Algorithms for Simple Graphs

For simple graphs, the paper rounds feasible knapsack-intersection solutions using source and sink vertices, with a deterministic source-sink split available for bipartite graphs. The section develops the rounding analyses and polynomial-time implementations for both settings.

3.1 General Simple Graphs

  • For general simple graphs, vertices are independently labeled as sources with probability q or sinks; source samples propose edges and each sink keeps a maximum-weight feasible subset.Distinct neighbors make the proposed incident edges independent at a sink, enabling the knapsack contention-resolution guarantee.Source: §3 · p. 9, §3.1 · pp. 9–10

3.1 General Simple Graphs; 3.2 Bipartite Simple Graphs

  • The general-graph rounding output satisfies every vertex-capacity constraint.The bipartite algorithm likewise satisfies all vertex capacities, and its analysis yields the stated integrality-gap bound.Source: §3.1 · p. 10, §3.2 · pp. 11–12

3.2 Bipartite Simple Graphs

  • For bipartite simple graphs, assigning one side as sources and the other as sinks deterministically avoids the loss from random labeling.The resulting knapsack-intersection LP integrality gap is at most 2.Source: §3.2 · pp. 11–12

3.3 Polynomial-Time Implementation

  • For simple graphs, the cited results give fully polynomial-time (3/2 + ε)- and (2 + ε)-approximation algorithms for general and bipartite simple graphs, respectively.Source: §3 · p. 9, §3.3 · p. 13

4 Rounding Algorithms for Multigraphs

Parallel edges can be correlated during rounding, so the multigraph approach bundles feasible parallel-edge subsets and extends the rounding framework to multiple-choice selections. Pareto approximation keeps the auxiliary instance polynomial in size.

4.1 Bundling Parallel Edges and Pareto Families

  • Bundling replaces feasible nonempty parallel-edge subsets with auxiliary edges, but the resulting graph may be exponentially large.A ξ-Pareto family keeps polynomially many representatives, each with no larger demand and at most a ξ-fractional loss in weight; the resulting optimum is at least (1 − ξ) times the original optimum.Source: §4 · p. 13, §4.1 · pp. 14–15

4.2 Multiple-Choice Demand Matching

  • The multiple-choice knapsack-intersection LP has an FPTAS, yielding a feasible solution with objective at least (1 − ε) times its optimum in time polynomial in 1/ε and input length.Source: §4.2 · p. 16

4.3 Multiple-Choice CR Scheme for the Integral Knapsack Polytope

  • Under multiple-choice sampling, the expected maximum feasible knapsack value is at least q/(1 + q) times w^T x when x is in the integral knapsack polytope and qx(π) ≤ 1 for every part.Source: §4.3 · p. 16

4.4 Rounding Algorithms for Multiple-Choice Demand Matching

  • The multigraph rounding algorithms use source-sink rounding with multiple-choice sampling, preserving the standard contention-resolution guarantee while allowing at most one selected edge per parallel-edge group.Their outputs satisfy both vertex capacities and the multiple-choice constraints.Source: §4.4 · pp. 17–18

4.5 Putting Everything Together

  • For Demand Matching, a randomized (2 + ε)-approximation is obtained, and both algorithms run in fully polynomial time because the ξ-Pareto auxiliary instance has size polynomial in 1/ξ and the input length.Source: §4.5 · p. 20

5 Concluding Remarks

The paper combines knapsack intersection relaxations with contention resolution to improve demand-matching approximation guarantees. Its concluding results also establish a tight knapsack contention-resolution balance and identify open directions.

5 Concluding Remarks

  • The algorithms achieve expected approximation ratios of 3/2 + √2 + ε ≈ 2.914 + ε for general graphs and 2 + ε for bipartite graphs, for every ε > 0.The general-graph result is the first approximation ratio strictly below 3 and uses a stronger formulation than the natural LP relaxation.Source: §5 · p. 20
  • For every q ∈ [0, 1], the integral knapsack polytope admits a (q, 1/(1 + q))-balanced contention resolution scheme, and this balance is worst-case optimal.The guarantee may also be useful in other packing problems with local knapsack constraints.Source: §5 · p. 20
  • Open questions include improving the approximation ratios, determining exact knapsack intersection LP integrality gaps, and finding applications of the contention-resolution guarantee.The authors also ask whether higher fixed levels of the knapsack intersection hierarchy improve guarantees and whether multigraph guarantees can be obtained by directly rounding the LP without auxiliary bundles.Source: §5 · p. 20

A Tightness of the Knapsack Contention Resolution Guarantee

The appendix constructs knapsack instances showing that the contention-resolution balance guarantee cannot be improved in the worst case. The construction pits one large item against many unit-demand items under sampling.

A Tightness of the Knapsack Contention Resolution Guarantee

  • The construction mixes two feasible solutions: one containing a single item that fills the knapsack and one containing many unit-demand items.Their weights are chosen so the large item approximates the expected total weight of the sampled unit-demand items; a feasible sampled subset takes either the large item or the unit-demand items, not both.Source: A Tightness of the Knapsack Contention… · p. 22
  • The construction sets capacity B = M^2 and n = M^2 + 1; its fractional vector has x_i = 1/M for i in [n−1] and x_n = 1−1/M.Source: A Tightness of the Knapsack Contention… · p. 22
  • As M grows, the sampled instance yields an expected selected-weight ratio below 1/(1 + q) + ε for sufficiently large M.The construction samples R := R(qx) and compares the best feasible subset's weight r(R, B) with q w^T x.Source: A Tightness of the Knapsack Contention… · pp. 22–23

B Polynomial-Time Construction of a Pareto Family

The appendix constructs a fully polynomial-time algorithm for Threshold Knapsack, a subproblem used to build a polynomial-cardinality Pareto family. It rounds weights, applies dynamic programming, and proves the returned set meets the target up to a controlled loss.

B Polynomial-Time Construction of a Pareto Family

  • Preprocessing discards items exceeding capacity and handles empty or zero-weight cases before constructing the Pareto family.Positive-weight sets can be restricted to positive-weight items without increasing demand or changing weight; zero-weight sets are represented by a minimum-demand remaining item.Source: B Polynomial-Time Construction of a… · p. 24
  • The algorithm rounds item weights so their total has polynomially many values, losing at most a φ-fraction of the target weight Ψ.It uses a knapsack dynamic program that finds a minimum-demand set for each rounded weight value.Source: B Polynomial-Time Construction of a… · p. 24
  • Threshold Knapsack can be solved in time polynomial in 1/φ and the input encoding length.The dynamic program performs O(|N|^2/φ) arithmetic operations, with table entries and indices of polynomial encoding length.Source: B Polynomial-Time Construction of a… · p. 24
  • If a feasible set reaches weight Ψ, the algorithm returns a feasible set of weight at least (1 − φ)Ψ and demand no greater than the minimum demand among sets reaching Ψ.If no set reaches Ψ, the algorithm can certify that fact.Source: B Polynomial-Time Construction of a… · p. 25

C An FPTAS for Multiple-Choice Knapsack Intersection LP

The appendix establishes a fully polynomial-time approximation scheme for the multiple-choice knapsack intersection LP. It uses approximate separation for the dual, then an ellipsoid-based procedure to obtain a feasible primal solution.

C An FPTAS for Multiple-Choice Knapsack Intersection LP

  • Each vertex configuration enforces both its capacity constraint and at most one selected edge from each parallel-edge group.The multiple-choice family Kmc(v) combines the local knapsack constraint with the partition Πv of incident edges.Source: C An FPTAS for Multiple-Choice… · p. 25
  • A multiple-choice knapsack FPTAS provides a β-approximate separation algorithm for the dual configuration LP.The separation step discards nonpositive-price items and searches for a violating configuration for each vertex.Source: C An FPTAS for Multiple-Choice… · pp. 26–27
  • The approximate-separation result yields a feasible primal configuration-LP solution with polynomial-size support in time polynomial in 1/ε and the input length.The multiple-choice knapsack LP is equivalent to the primal configuration LP.Source: C An FPTAS for Multiple-Choice… · pp. 26–27
  • The ellipsoid algorithm tests dual feasibility systems and binary search finds the smallest feasible objective threshold.The algorithm uses a polynomial set of checked constraints to form a restricted primal LP, then extends its solution to the full primal LP.Source: C An FPTAS for Multiple-Choice… · pp. 27–28
Loading 2609.17932v1…