Y, Cao and R B, Sandeep
(2017)
Minimum fillin: Inapproximability and almost tight lower bounds.
In: Annual ACMSIAM Symposium on Discrete Algorithms, SODA, 1617 January, 2017, Hotel Porta FiraBarcelona; Spain.
Full text not available from this repository.
(
Request a copy)
Abstract
Performing Gaussian elimination to a sparse matrix may turn some zeroes into nonzero values, so called fillins, which we want to minimize to keep the matrix sparse. Let n denote the rows of the matrix and k the number of fillins. For the minimum fillin 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]
Actions (login required)

View Item 