Mourad Baïou, Francisco Barahona
Networks
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.
Mourad Baïou, Francisco Barahona
Networks
Jianke Yang, Robin Walters, et al.
ICML 2023
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems