Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

DOI10.1137/1.9781611974782.55zbMath1410.68141MaRDI QIDQ4575794

Yixin Cao, R. B. Sandeep

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

65F50: Computational methods for sparse matrices

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)