Back to Search
Start Over
SUPERLINEAR INTEGRALITY GAPS FOR THE MINIMUM MAJORITY PROBLEM.
- Source :
-
SIAM Journal on Discrete Mathematics . 2021, Vol. 35 Issue 4, p3004-3016. 13p. - Publication Year :
- 2021
-
Abstract
- The minimum majority problem is as follows: given a matrix $A \in \{-1, 1\}^{m \times n}$, minimize $\sum_{i=1}^n x_i$ subject to $A {x} \geq {1}$ and ${x} \in ({\mathbb Z}^+)^n$. An approximation algorithm that finds a solution with value $O({opt}^2 \log m)$ in ${poly}(m,n,{opt})$ time is known, which can be obtained by rounding a linear programming relaxation. We establish integrality gaps that limit the prospects for improving upon this guarantee through improved rounding and/or the application of Lovász--Schrijver (LS) or Sherali--Adams (SA) tightening of the relaxation. These gaps show that applying LS and SA relaxations cannot improve upon the $O({opt}^2 \log m)$ guarantee by more than a constant factor in polynomial time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 35
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 154646129
- Full Text :
- https://doi.org/10.1137/20M1359584