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

K.M. Elbassioni, R. Raman, Saurabh Ray, R.A. Sitters

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)
2 Downloads (Pure)


Given a system of constraints li = aTix = ui, where ai ¿ {0, 1}n, and li, ui ¿ R+, for i = 1,..., m, we consider the problem Mrfs of finding the largest subsystem for which there exists a feasible solution x = 0. We present approximation algorithms and inapproximability results for this problem, and study some important special cases. Our main contributions are: 1. In the general case, where ai e {0, 1}n, a sharp separation in the approximability between the case when L = max{l1, ..., lm} is bounded above by a polynomial in n and m, and the case when it is not. 2. In the case where A is an interval matrix, a sharp separation in approximability between the case where we allow a violation of the upper bounds by at most a (1 + e) factor, for any fixed e > 0 and the case where no violations are allowed. Along the way, we prove that the induced matching problem on bipartite graphs is inapproximable beyond a factor of O(n1/3-e), for any e > 0 unless NP=ZPP. Finally, we also show applications of Mrfs to some recently studied pricing problems.
Original languageEnglish
Title of host publicationProceedings 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09, New York NY, USA, January 4-6, 2009)
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Publication statusPublished - 2009


Dive into the research topics of 'On the approximability of the maximum feasible subsystem problem with 0/1-coefficients'. Together they form a unique fingerprint.

Cite this