Minimum fill-in: Inapproximability and almost tight lower bounds

Y, Cao and R B, Sandeep (2017) Minimum fill-in: Inapproximability and almost tight lower bounds. In: Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 16-17 January, 2017, Hotel Porta FiraBarcelona; Spain.

Full text not available from this repository. (Request a copy)


Performing Gaussian elimination to a sparse matrix may turn some zeroes into nonzero values, so called fill-ins, which we want to minimize to keep the matrix sparse. Let n denote the rows of the matrix and k the number of fill-ins. For the minimum fill-in problem, we exclude the existence of polynomial time approximation schemes, assuming P6=NP, and the existence of 2O(n1)-time approximation schemes for any positive , assuming the Exponential Time Hypothesis. Also implied is a 2O(k1=2) nO(1) parameterized lower bound. Behind these results is a new reduction from vertex cover, which might be of its own interest: All previous reductions for similar problems are from some kind of graph layout problems.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 11 Apr 2017 06:32
Last Modified: 11 Apr 2017 06:32
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 3161 Statistics for this ePrint Item