EUVIMEDEUVIMED entdecken
Crossref

Asymptotically Optimal Hardness for \({k}\)-Set Packing and \({k}\)-Matroid Intersection

Euiwoong Lee, Ola Svensson, Theophile Thiery

SIAM Journal on Computing · 30.10.2026 · STOC25-81-STOC25-94

DOI: 10.1137/25m1781206 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 30.10.2026. Verfasst von Euiwoong Lee und 2 weiteren Autor:innen. Die Arbeit nennt 31 Literaturangaben. Gefördert von: National Science Foundation, Swiss State Secretariat for Education Research and Innovation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For any [Formula: see text], we prove that [Formula: see text]-Dimensional Matching is hard to approximate within a factor of [Formula: see text] for large [Formula: see text] unless [Formula: see text]. Listed in Karp’s 21 [Formula: see text]-complete problems, [Formula: see text]-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: [Formula: see text]-Set Packing, [Formula: see text]-Matroid Intersection, and Matroid [Formula: see text]-Parity. For all the aforementioned problems, the best-known lower bound was a [Formula: see text]-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieve an approximation of [Formula: see text]. Our result narrows down this gap to a constant and thus provides a rationale for the observed algorithmic difficulties. The crux of our result hinges on a novel approximation preserving gadget from [Formula: see text]-degree bounded [Formula: see text]-CSPs over alphabet size [Formula: see text] to [Formula: see text]-Dimensional Matching. Along the way, we prove that [Formula: see text]-degree bounded [Formula: see text]-CSPs over alphabet size [Formula: see text] are hard to approximate within a factor [Formula: see text] using known randomised sparsification methods for CSPs.

Förderung

  • National Science Foundation
  • Swiss State Secretariat for Education Research and Innovation

Zitieren

APA

Lee, E., Svensson, O., & Thiery, T. (2026). Asymptotically Optimal Hardness for \({k}\)-Set Packing and \({k}\)-Matroid Intersection. SIAM Journal on Computing, STOC25-81-STOC25-94. https://doi.org/10.1137/25m1781206

Vancouver

Lee E, Svensson O, Thiery T. Asymptotically Optimal Hardness for \({k}\)-Set Packing and \({k}\)-Matroid Intersection. SIAM Journal on Computing. 2026:STOC25-81-STOC25-94. doi:10.1137/25m1781206

BibTeX
@article{Lee2026,
  author = {Lee, Euiwoong and Svensson, Ola and Thiery, Theophile},
  title = {Asymptotically Optimal Hardness for \(k\)-Set Packing and \(k\)-Matroid Intersection},
  journal = {SIAM Journal on Computing},
  year = {2026},
  pages = {STOC25--81--STOC25--94},
  doi = {10.1137/25m1781206}
}
Kostenlos starten →