Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

DOI10.1137/1.9781611974782.55zbMath1410.68141OpenAlexW2469815617MaRDI QIDQ4575794

R. B. Sandeep, Yixin Cao

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.55

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Unnamed Item ⋮ Approximation algorithms in combinatorial scientific computing

This page was built for publication: Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds