Complexity of minimum irreducible infeasible subsystem covers for flow networks

DOI10.1016/j.dam.2018.02.025zbMath1387.05243OpenAlexW2793983615MaRDI QIDQ1752598

Marc E. Pfetsch, Imke Joormann

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.02.025

zbMATH Keywords

infeasibility analysisfixed parameter tractableflow networkminimum IIS cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Flows in graphs (05C21)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A theorem on flows in networks
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• The facets of the polyhedral set determined by the Gale-Hoffman inequalities
• Some results concerning post-infeasibility analysis
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• How to compute least infeasible flows
• Consistency, redundancy, and implied equalities in linear systems
• Finding the minimum weight IIS cover of an infeasible system of linear inequalities
• An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem
• A note on resolving infeasibility in linear programs by constraint relaxation
• The minimum shift design problem
• Feasibility and infeasibility in optimization. Algorithms and computational methods.
• Fast Heuristics for the Maximum Feasible Subsystem Problem
• Evaluating Gas Network Capacities
• Diagnosing Infeasibility in Min-cost Network Flow Problems Part II: Primal Infeasibility
• Easy problems for tree-decomposable graphs
• Branch-and-Cut for the Maximum Feasible Subsystem Problem
• Diagnosing Infeasibility in Min-cast Network Flow Problems Part I: Dual Infeasibility
• Identifying Minimally Infeasible Subsystems of Inequalities
• A search strategy for the elementary cycles of a directed graph
• On Algorithms for Enumerating All Circuits of a Graph
• A characterization of irreducible infeasible subsystems in flow networks
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks