Dual Cheeger Constants, Signless 1-Laplacians and Maxcut

Sihong Shao, Chuan Yang, Dong Zhang

The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem, whose optimal value is referred to the dual…