Characterization of line width variation
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
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.
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994
A.R. Conn, Nick Gould, et al.
Mathematics of Computation
Fernando Martinez, Juntao Chen, et al.
AAAI 2025