Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
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.
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008