Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Given a graph with nonnegative edge-weights, let f(k) be the value of an optimal solution of the k-cut problem. We study f as a function of k. Let g be the convex envelope of f. We give a polynomial algorithm to compute g. In particular, if f is convex, then it can be computed in polynomial time for all k. We show some experiments in computing g.
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Jianke Yang, Robin Walters, et al.
ICML 2023
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Naga Ayachitula, Melissa Buco, et al.
SCC 2007