Generative Adversarial Symmetry Discovery
Jianke Yang, Robin Walters, et al.
ICML 2023
This note presents improved approximation guarantees for the requirement cut problem: given an n-vertex edge-weighted graph G=(V,E), and g groups of vertices X1,...,Xg ⊆ V with each group Xi having a requirement ri between 0 and |Xi|, the goal is to find a minimum cost set of edges whose removal separates each group Xi into at least ri disconnected components. We give a tight Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk·logg) approximation ratio for general graphs, where k=|∪gi=1=1gXi|≤n. © 2010 Elsevier B.V. All rights reserved.
Jianke Yang, Robin Walters, et al.
ICML 2023
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000