Title:Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection
| Speaker: | Euiwoong Lee |
| Affiliation: | University of Michigan |
| Location: | MC 5501 |
Abstract: For any epsilon > 0, we prove that k-Dimensional Matching is hard to approximate within a factor of k/(12 + epsilon) for large k unless NP \subseteq BPP. Listed in Karp's 21 NP-complete problems, k-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: k-Set Packing, k-Matroid Intersection, and Matroid k-Parity. For all the aforementioned problems, the best known lower bound was an Omega(k /log(k))-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieved an approximation of O(k). Our result narrows down this gap to a constant and thus provides a rationale for the observed algorithmic difficulties.