TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Resolving infeasibility of linear systems: a parameterized approach
 
Options

Resolving infeasibility of linear systems: a parameterized approach

Citation Link: https://doi.org/10.15480/882.2623
Publikationstyp
Conference Paper
Date Issued
2019-12
Sprache
English
Author(s)
Göke, Alexander  
Mendoza Cadena, Lydia Mirabel  
Mnich, Matthias  
Institut
Algorithmen und Komplexität E-11  
TORE-DOI
10.15480/882.2623
TORE-URI
http://hdl.handle.net/11420/4603
First published in
Leibniz International Proceedings in Informatics (LIPIcs)  
Number in series
148
Article Number
17
Citation
International Symposium on Parameterized and Exact Computation (IPEC 2019)
Contribution to Conference
14th International Symposium on Parameterized and Exact Computation, IPEC 2019  
Publisher DOI
10.4230/LIPIcs.IPEC.2019.17
Scopus ID
2-s2.0-85077441638
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).
Subjects
Fixed-parameter algorithms
Infeasible subsystems
Linear programming
DDC Class
004: Informatik
More Funding Information
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.
Lizenz
https://creativecommons.org/licenses/by/3.0/de/
Loading...
Thumbnail Image
Name

LIPIcs-IPEC-2019-17.pdf

Size

656.29 KB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback