DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2019.17

Resolving Infeasibility of Linear Systems: A Parameterized Approach

Authors: Alexander Göke, Lydia Mirabel Mendoza Cadena, and Matthias Mnich

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract

Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to inaccuracies of the data or modeling errors, in practical applications one often faces linear systems that are infeasible. Extensive theoretical and practical methods have been proposed for post-infeasibility analysis of linear systems. This generally amounts to detecting a feasibility blocker of small size k, which is a set of equations and inequalities whose removal or perturbation from the large system of size m yields a feasible system. This motivates a parameterized approach towards post-infeasibility analysis, where we aim to find a feasibility blocker of size at most k in fixed-parameter time f(k)* m^{O(1)}. On the one hand, we establish parameterized intractability (W[1]-hardness) results even in very restricted settings. On the other hand, we develop fixed-parameter algorithms parameterized by the number of perturbed inequalities and the number of positive/negative right-hand sides. Our algorithms capture the case of Directed Feedback Arc Set, a fundamental parameterized problem whose fixed-parameter tractability was shown by Chen et al. (STOC 2008).

Cite as

Alexander Göke, Lydia Mirabel Mendoza Cadena, and Matthias Mnich. Resolving Infeasibility of Linear Systems: A Parameterized Approach. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{goke_et_al:LIPIcs.IPEC.2019.17,
  author =	{G\"{o}ke, Alexander and Mendoza Cadena, Lydia Mirabel and Mnich, Matthias},
  title =	{{Resolving Infeasibility of Linear Systems: A Parameterized Approach}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.17},
  URN =		{urn:nbn:de:0030-drops-114787},
  doi =		{10.4230/LIPIcs.IPEC.2019.17},
  annote =	{Keywords: Infeasible subsystems, linear programming, fixed-parameter algorithms}
}

Search Results

Documents authored by Mendoza Cadena, Lydia Mirabel

Resolving Infeasibility of Linear Systems: A Parameterized Approach

Abstract

Cite as

Thanks for your feedback!

Could not send message