Superlinear integrality gaps for the minimum majority problem

The minimum majority problem is as follows: given an m-by-n matrix A with {-1,1} entries, minimize x_1 + ... + x_n subject to A x > 0 for x = (x_1,...,x_n), where x_1,...,x_n are non-negative integers. An approximation algorithm that finds a solution with value O(opt^2 log m) in poly(m,n,opt) is known, which can be obtained by rounding a linear programming relaxation. We establish integrality gaps that limit the prospects for improving on this guarantee through improved rounding and/or the application of Lov'asz-Schrijver or Sherali-Adams tightening of the relaxation. These gaps show that these methods cannot improve on the O(opt^2 log m) guarantee by more than a constant factor in polynomial time.

• Machine Intelligence