Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing
verfasst von : Peter Damaschke
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A vector with at most
k
nonzeros is called
k
-sparse. We show that enumerating the support vectors of
k
-sparse solutions to a system
Ax
=
b
of
r
-sparse linear equations (i.e., where the rows of
A
are
r
-sparse) is fixed-parameter tractable (FPT) in the combined parameter
r
,
k
. For
r
= 2 the problem is simple. For 0,1-matrices
A
we can also compute an
O
(
rk
r
) kernel. For systems of linear inequalities we get an FPT result in the combined parameter
d
,
k
, where
d
is the total number of minimal solutions. This is achieved by interpeting the problem as a case of group testing in the complex model. The problems stem from the reconstruction of chemical mixtures by observable reaction products.