The complexity and approximability of finding maximum feasible subsystems of linear relations
From MaRDI portal
Publication:1367542
DOI10.1016/0304-3975(94)00254-GzbMath0884.68093OpenAlexW2049083558MaRDI QIDQ1367542
Publication date: 29 September 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00254-g
Related Items (48)
The maximum feasible subset problem (maxFS) and applications ⋮ Robust regression via error tolerance ⋮ On a class of optimization problems with no ``efficiently computable solution ⋮ The MIN PFS problem and piecewise linear model estimation ⋮ Global optimization for low-dimensional switching linear regression and bounded-error estimation ⋮ Applications of regularized least squares to pattern classification ⋮ ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs ⋮ The hardness of approximate optima in lattices, codes, and systems of linear equations ⋮ Matrix sparsification and the sparse null space problem ⋮ Mechanisms for information elicitation ⋮ Quantile-Based Iterative Methods for Corrupted Systems of Linear Equations ⋮ 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 ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ Covering Linear Programming with Violations ⋮ Error-free and best-fit extensions of partially defined Boolean functions ⋮ Faster maximum feasible subsystem solutions for dense constraint matrices ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ Public Bayesian persuasion: being almost optimal and almost persuasive ⋮ Robust fitting in computer vision: easy or hard? ⋮ On the difficulty of approximately maximizing agreements. ⋮ A Subgradient-Based Approach for Finding the Maximum Feasible Subsystem with Respect to a Set ⋮ On the establishment of distinct identities in overlay networks ⋮ Distinguishing string selection problems. ⋮ A two-phase relaxation-based heuristic for the maximum feasible subsystem problem ⋮ A reformulation-linearization-convexification algorithm for optimal correction of an inconsistent system of linear constraints ⋮ Irreducible infeasible sets in convex mixed-integer programs ⋮ Complexity of minimum irreducible infeasible subsystem covers for flow networks ⋮ Optimization approaches to supervised classification ⋮ Approximating maximum satisfiable subsystems of linear equations of bounded width ⋮ Feasible partition problem in reverse convex and convex mixed-integer programming ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Inapproximability results for equations over infinite groups ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ A local Vapnik-Chervonenkis complexity ⋮ Maximizing agreements with one-sided error with applications to heuristic learning ⋮ Discovering and Exploiting Statistical Properties for Query Optimization in Relational Databases: A Survey ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ On the hardness of approximating shortest integer relations among rational numbers ⋮ Integer programming as a framework for optimization and approximability ⋮ Some APX-completeness results for cubic graphs ⋮ Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions ⋮ On optimal zero-preserving corrections for inconsistent linear systems ⋮ Derandomized graph products ⋮ On approximate learning by multi-layered feedforward circuits ⋮ Complexity and approximation of the smallest \(k\)-enclosing ball problem ⋮ Logical analysis of binary data with missing bits ⋮ Maximizing agreements and coagnostic learning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximate solution of NP optimization problems
- A well-characterized approximation problem
- A new polynomial-time algorithm for linear programming
- Completeness in approximation classes
- Trees and hills: methodology for maximizing functions of systems of linear relations
- Explicit construction of linear sized tolerant networks
- Ramanujan graphs
- On the complexity of approximating the independent set problem
- Optimization, approximation, and complexity classes
- Quantifiers and approximation
- Approximation algorithms for combinatorial problems
- The densest hemisphere problem
- Logical definability of NP optimization problems
- Derandomized graph products
- An Algorithm for the Optimal Solution of Linear Inequalities and its Application to Pattern Recognition
- Approaches to Diagnosing Infeasible Linear Programs
- On Syntactic versus Computational Views of Approximability
- On the Approximation of Maximum Satisfiability
- On the hardness of approximating minimization problems
- Polynomially bounded minimization problems which are hard to approximate
- Efficient probabilistically checkable proofs and applications to approximations
This page was built for publication: The complexity and approximability of finding maximum feasible subsystems of linear relations
