Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.2623
Publisher DOI: 10.4230/LIPIcs.IPEC.2019.17
Title: Resolving infeasibility of linear systems: a parameterized approach
Language: English
Authors: Göke, Alexander 
Mendoza Cadena, Lydia Mirabel 
Mnich, Matthias  
Keywords: Fixed-parameter algorithms;Infeasible subsystems;Linear programming
Issue Date: Dec-2019
Source: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Part of Series: Leibniz International Proceedings in Informatics (LIPIcs) 
Volume number: 148
Abstract (english): 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) · mO(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).
Conference: 14th International Symposium on Parameterized and Exact Computation, IPEC 2019 
URI: http://hdl.handle.net/11420/4603
DOI: 10.15480/882.2623
ISBN: 978-3-95977-129-0
ISSN: 1868-8969
Institute: Algorithmen und Komplexität E-11 
Type: InProceedings (Aufsatz / Paper einer Konferenz etc.)
Funded by: Supported by DAAD with funds of the Bundesministerium für Bildung und Forschung (BMBF) and by DFG project MN 59/1-1. Supported by DAAD with funds of the Bundesministerium für Bildung und Forschung (BMBF) and by DFG project MN 59/4-1.
License: CC BY 3.0 DE (Namensnennung) CC BY 3.0 DE (Namensnennung)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
LIPIcs-IPEC-2019-17.pdfVerlags-PDF656,29 kBAdobe PDFThumbnail
View/Open
Show full item record

Page view(s)

172
Last Week
3
Last month
30
checked on Nov 30, 2020

Download(s)

18
checked on Nov 30, 2020

Google ScholarTM

Check

Note about this record

Export

This item is licensed under a Creative Commons License Creative Commons