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.68127OpenAlexW2131716254MaRDI 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
Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Chemistry (general) in thermodynamics and heat transfer (80A50)
Related Items (2)
Parameterized complexity of sparse linear complementarity problems ⋮ A note on sparse solutions of sparse linear systems
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
This page was built for publication: Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing