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

Khaled Elbassioni, Rajiv Raman, Saurabh Ray, René Sitters

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a system of constraints ℓi ≤ ai T x ≤ ui, where ai ∈ {0,1}n, and ℓi, ui ∈ ℝ+, 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 ∈ {0, 1}n, a sharp separation in the approximability between the case when L = max{ℓ1, . . . , ℓm} 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 + ∈) factor, for any fixed ∈ > 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 Ω(n1/3-∈), for any ∈ > 0 unless NP=ZPP. Finally, we also show applications of MRFS to some recently studied pricing problems.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery (ACM)
Pages1210-1219
Number of pages10
ISBN (Print)9780898716801
DOIs
StatePublished - 2009
Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
Duration: Jan 4 2009Jan 6 2009

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew York, NY
Period1/4/091/6/09

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint 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