CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Sparse solutions of sparse linear systems: Fixed-parameter tractability and an application of complex group testing

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
Lecture Notes in Computer Science. 6th International Symposium on Parameterized and Exact Computation, Saarbrucken, 6-8 September 2011 (0302-9743). Vol. 7112 (2011), p. 94-105.
[Konferensbidrag, refereegranskat]

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 a 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 interpreting 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.

Nyckelord: sparse vector, linear system, hitting set, parameterized algorithm, enumeration, problem kernel, group testing

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2012-04-01. Senast ändrad 2015-02-11.
CPL Pubid: 156331


Läs direkt!

Länk till annan sajt (kan kräva inloggning)