Sparse integrality-gap conjecture for random hitting set

From papers

Let mm be the number of subsets, let pp be the inclusion probability, and let nn be the number of elements. Write valGR\operatorname{val}_{\mathrm{GR}} for the value produced by the greedy algorithm, valIP\operatorname{val}_{\mathrm{IP}} for the integer-program value, and valLP\operatorname{val}_{\mathrm{LP}} for the linear-programming relaxation. Let C1C_1 be a constant. Sparse conjecture. For 1mplogn1 \lesssim mp \ll \log n,

valGRvalIP1,valIPvalLPC1,\frac{\operatorname{val}_{\mathrm{GR}}}{\operatorname{val}_{\mathrm{IP}}} \to 1, \qquad \frac{\operatorname{val}_{\mathrm{IP}}}{\operatorname{val}_{\mathrm{LP}}} \to C_1,

where 1<C1<1.51<C_1<1.5. This conjecture describes the intermediate-sparsity regime and predicts both asymptotic optimality of the greedy algorithm relative to the integer program and a bounded nontrivial integrality gap. The source formulates it from numerical experiments and gives no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Gabriel Arpino, Daniil Dmitriev and Nicolo Grometto, “Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem”, arXiv:2305.05565 (2023).

Solutions 0

No solutions have been posted yet.