Google Research

Superlinear integrality gaps for the minimum majority problem

FOCS (2022) (to appear)

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.

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work