Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Göke, Alexander; Mendoza Cadena, Lydia Mirabel; Mnich, Matthias https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URL:

; ;

Resolving Infeasibility of Linear Systems: A Parameterized Approach

pdf-format:


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).

BibTeX - Entry

@InProceedings{gke_et_al:LIPIcs:2019:11478,
  author =	{Alexander G{\"o}ke and Lydia Mirabel Mendoza Cadena and Matthias Mnich},
  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 =	{Bart M. P. Jansen and Jan Arne Telle},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11478},
  doi =		{10.4230/LIPIcs.IPEC.2019.17},
  annote =	{Keywords: Infeasible subsystems, linear programming, fixed-parameter algorithms}
}

Keywords: Infeasible subsystems, linear programming, fixed-parameter algorithms
Seminar: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Issue date: 2019
Date of publication: 04.12.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI