Motion video analysis using planar parallax
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994
In the Steiner Network problem, we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u, v. The goal is to find a minimum-cost subgraph H of G that contains ruv edge-disjoint paths for all u, v ∈ V. In Prize-Collecting Steiner Network problems, we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when ruv ∈ {0, 1} is the classic Prize-Collecting Steiner Forest problem. In this article, we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone nondecreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed by Nagarajan et al. [2008]. We further generalize our results for element-connectivity and node-connectivity. © 2012 ACM.
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994
James Lee Hafner
Journal of Number Theory
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991