Speaker
Daniil Dmitriev
(ETH Zurich)
Description
For the standard vertex cover problem, linear relaxation has integrality gap 2. In our work, we explore an extension of this problem by considering i) random hyperedges and ii) low degree vertices. We conjecture the value of the integrality gap and prove almost tight upper and lower bounds. Based on joint work with N. Grometto, G. Arpino, R. Barboni and A. Bandeira.
