Metraipolis › archive › dc_00a9bdec480b

Integrality gap preserving reductions — arXiv:2609.19967

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.19967
License (as archived): CC0-1.0
Archived: 2026-10-10T05:44:47.948Z
SHA-256 of the archived text: c861b7ccb1ee515314e61435f3c9f277a4bc37ab66064b30071548cdbe5a7a45
Stable URL of this page: https://metraipolis.com/documento/dc_00a9bdec480b

How to cite

Integrality gap preserving reductions — arXiv:2609.19967 — arXiv (en), https://arxiv.org/abs/2609.19967 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_00a9bdec480b (Metraipolis archive dc_00a9bdec480b, sha256 c861b7ccb1ee515314e61435f3c9f277a4bc37ab66064b30071548cdbe5a7a45)

BibTeX

@misc{dc00a9bdec480b,
  title = {Integrality gap preserving reductions — arXiv:2609.19967},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.19967},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_00a9bdec480b; sha256 c861b7ccb1ee515314e61435f3c9f277a4bc37ab66064b30071548cdbe5a7a45},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19967. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, called \emph{integrality gap preserving reduction}, consists of iteratively shrinking the input universe of the problem while guaranteeing that gap-maximizing instances remain selected. When the subset of remaining instances becomes specific enough, we calculate the integrality gap explicitly. Besides applying integrality gap preserving reductions to three well-known optimization problems via their standard linear programming formulations (weighted vertex cover problem, multiple knapsack problem, and unrelated machine scheduling problem), we analyse the restricted assignment problem via its configuration LP relaxation. We prove that the integrality gap is equal to $1$ for three ``easy'' subclasses of the problem that are either solvable in polynomial time or admit a PTAS (e.g., the all-one processing time case). For some remaining cases, we improve the current lower bound using our technique.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in cs.DS).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.19967 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T05:08:06.589Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).