Superlinear integrality gaps for the minimum majority problem
Abstract
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.
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.
Research Areas
