Da-Ke He, Ashish Jagmohan, et al.
ISIT 2007
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.
Da-Ke He, Ashish Jagmohan, et al.
ISIT 2007
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997