Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
From MaRDI portal
Publication:392033
DOI10.1016/j.tcs.2012.07.001zbMath1358.68127MaRDI QIDQ392033
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.001
linear system; enumeration; group testing; parameterized algorithm; hitting set; problem kernel; sparse vector
65F50: Computational methods for sparse matrices
68Q25: Analysis of algorithms and problem complexity
05C65: Hypergraphs
80A50: Chemistry (general) in thermodynamics and heat transfer
Related Items
A note on sparse solutions of sparse linear systems, Parameterized complexity of sparse linear complementarity problems
Cites Work
- Unnamed Item
- Unnamed Item
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- A competitive algorithm in searching for many edges in a hypergraph
- An efficient fixed-parameter algorithm for 3-hitting set
- Parameterized algorithms for \(d\)-hitting set: the weighted case
- The union of minimal hitting sets: parameterized combinatorial bounds and counting
- A group testing problem for graphs with several defective edges
- A group testing problem for hypergraphs of bounded rank
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- On the Uniqueness of Nonnegative Sparse Solutions to Underdetermined Systems of Equations
- A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
- Sparse Approximate Solutions to Linear Systems
- Sparse nonnegative solution of underdetermined linear equations by linear programming
