Breaking the $\sqrt{3}$ Barrier for Maximum Weighted $3$-Set Packing
A deterministic polynomial-time approximation for Maximum Weighted $3-Set Packing, breaking the $\sqrt3$ locality-gap barrier of squared-weight local search and proving that $\sqrt3$ is a locality-gap lower bound for the squared-weight objective even with exchanges of arbitrary size.
Wei-Tian Tong, Yao Xu
· 0 citations