The complexity and approximability of finding maximum feasible subsystems of linear relations
type: Item
instance of: scholarly article
title: The complexity and approximability of finding maximum feasible subsystems of linear relations
zbMATH Open document ID: 0884.68093
DOI: 10.1016/0304-3975(94)00254-G
author: E. Amaldi
author: Viggo Kann
published in: Theoretical Computer Science
publication date: 1997-09-29T00:00:00Z
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 1065143
zbMATH Keywords: maximum feasible subsystem
MaRDI profile type: MaRDI publication profile
cites work: Derandomized graph products
cites work: Explicit construction of linear sized tolerant networks
cites work: Q4230322
cites work: Approximate solution of NP optimization problems
cites work: Efficient probabilistically checkable proofs and applications to approximations
cites work: On the complexity of approximating the independent set problem
cites work: Completeness in approximation classes
cites work: Q4403756
cites work: Q4198056
cites work: Approaches to Diagnosing Infeasible Linear Programs
cites work: Trees and hills: methodology for maximizing functions of systems of linear relations
cites work: Q3713398
cites work: A well-characterized approximation problem
cites work: Approximation algorithms for combinatorial problems
cites work: The densest hemisphere problem
cites work: Q4230352
cites work: Polynomially bounded minimization problems which are hard to approximate
cites work: A new polynomial-time algorithm for linear programming
cites work: On Syntactic versus Computational Views of Approximability
cites work: Logical definability of NP optimization problems
cites work: Ramanujan graphs
cites work: On the hardness of approximating minimization problems
cites work: Quantifiers and approximation
cites work: Optimization, approximation, and complexity classes
cites work: Q3818127
cites work: An Algorithm for the Optimal Solution of Linear Inequalities and its Application to Pattern Recognition
cites work: On the Approximation of Maximum Satisfiability
full work available at URL: 0304-3975(94)00254-g
OpenAlex ID: W2049083558
Recommended article: On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Recommended article: Q4263701
Recommended article: On the hardness of approximating max-satisfy
Recommended article: Approximating maximum satisfiable subsystems of linear equations of bounded width
description: scientific article; zbMATH DE number 1065143