On the approximability of the maximum feasible subsystem problem with 0/1-coefficients

MaRDI QIDQ4633936zbMATH OpenFDO

Authors Rajiv Raman, Saurabh Ray, Khaled Elbassioni, René A. Sitters

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496901

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1342119
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• On the maximum feasible subsystem problem, IISs and IIS-hypergraphs
• Branch-and-Cut for the Maximum Feasible Subsystem Problem
• Approximability of sparse integer programs

Cited in

(8)

• On the approximability of the maximum interval constrained coloring problem
• Complexity and approximability of parameterized MAX-CSPs
• Pricing on paths: a PTAS for the highway problem
• On the maximum uniquely restricted matching for bipartite graphs
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Hardness of computing width parameters based on branch decompositions over the vertex set
• Structural parameterizations for induced and acyclic matching

This page was built for publication: On the approximability of the maximum feasible subsystem problem with 0/1-coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633936)