Asymptotically Optimal Hardness for \({k}\)-Set Packing and \({k}\)-Matroid Intersection
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.
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}
}
EUVIMED