Sherali-Adams Integrality Gaps Matching the Log-Density Threshold

Eden Chlamtáč, Pasin Manurangsi

The log-density method is a powerful algorithmic framework which in recent years has given rise to the best-known approximations for a variety of problems, including Densest-$k$-Su…