The complexity and approximability of finding maximum feasible subsystems of linear relations
From MaRDI portal
Publication:1367542
DOI10.1016/0304-3975(94)00254-GzbMATH Open0884.68093OpenAlexW2049083558MaRDI QIDQ1367542FDOQ1367542
Authors: E. Amaldi, Viggo Kann 
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
Recommendations
Cites Work
- Title not available (Why is that?)
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Optimization, approximation, and complexity classes
- Ramanujan graphs
- Explicit construction of linear sized tolerant networks
- Derandomized graph products
- A well-characterized approximation problem
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- On the complexity of approximating the independent set problem
- Approximate solution of NP optimization problems
- Completeness in approximation classes
- Efficient probabilistically checkable proofs and applications to approximations
- The densest hemisphere problem
- Title not available (Why is that?)
- On Syntactic versus Computational Views of Approximability
- On the Approximation of Maximum Satisfiability
- Logical definability of NP optimization problems
- Title not available (Why is that?)
- Quantifiers and approximation
- Polynomially bounded minimization problems which are hard to approximate
- An Algorithm for the Optimal Solution of Linear Inequalities and its Application to Pattern Recognition
- Approaches to Diagnosing Infeasible Linear Programs
- Trees and hills: methodology for maximizing functions of systems of linear relations
Cited In (55)
- Cardinality minimization, constraints, and regularization: a survey
- A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
- Sublinear P system solutions to NP-complete problems
- Maximizing agreements with one-sided error with applications to heuristic learning
- The MaxSAT problem in the real-valued MV-algebra
- Approximating maximum satisfiable subsystems of linear equations of bounded width
- A subgradient-based approach for finding the maximum feasible subsystem with respect to a set
- Towards Finding Maximal Subrelations with Desired Properties
- Inapproximability results for equations over infinite groups
- Complexity and approximability of parameterized MAX-CSPs
- Applications of regularized least squares to pattern classification
- On approximate learning by multi-layered feedforward circuits
- Quantile-based iterative methods for corrupted systems of linear equations
- Computing the spark: mixed-integer programming for the (vector) matroid girth problem
- Complexity and approximation of the smallest \(k\)-enclosing ball problem
- On the hardness of approximating shortest integer relations among rational numbers
- Complexity of minimum irreducible infeasible subsystem covers for flow networks
- On a class of optimization problems with no ``efficiently computable solution
- Some APX-completeness results for cubic graphs
- An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem
- Finding the minimum weight IIS cover of an infeasible system of linear inequalities
- The maximum feasible subset problem (maxFS) and applications
- Distinguishing string selection problems.
- A local Vapnik-Chervonenkis complexity
- Optimization approaches to supervised classification
- Global optimization for low-dimensional switching linear regression and bounded-error estimation
- Public Bayesian persuasion: being almost optimal and almost persuasive
- Matrix sparsification and the sparse null space problem
- A reformulation-linearization-convexification algorithm for optimal correction of an inconsistent system of linear constraints
- Maximizing agreements with one-sided error with applications to heuristic learning
- Derandomized graph products
- Discovering and Exploiting Statistical Properties for Query Optimization in Relational Databases: A Survey
- Mechanisms for information elicitation
- Finding maximum linear subsystems of nonlinear systems with outputs
- On the establishment of distinct identities in overlay networks
- Faster maximum feasible subsystem solutions for dense constraint matrices
- Covering linear programming with violations
- Robust regression via error tolerance
- On optimal zero-preserving corrections for inconsistent linear systems
- Integer programming as a framework for optimization and approximability
- The generalized definitions of the two-dimensional largest common substructure problems
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Irreducible infeasible sets in convex mixed-integer programs
- Feasible partition problem in reverse convex and convex mixed-integer programming
- Logical analysis of binary data with missing bits
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- The MIN PFS problem and piecewise linear model estimation
- A two-phase relaxation-based heuristic for the maximum feasible subsystem problem
- Robust fitting in computer vision: easy or hard?
- On the difficulty of approximately maximizing agreements.
- Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions
- Error-free and best-fit extensions of partially defined Boolean functions
- ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs
- On the largest input-output linearizable subsystem
- Maximizing agreements and coagnostic learning
This page was built for publication: The complexity and approximability of finding maximum feasible subsystems of linear relations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1367542)
