Design And Analysis Of Approximation Algorithms – Ding – Zhu Du

the longer edges of W are horizontal line segments. Then the guillotine cut on W is a vertical (1/3, 2/3)-restricted cut of W; that is, it is a vertical line that intersects each longer edge of W in the middle third of that edge. Furthermore, this line is chosen to have, among all such vertical (1/3, 2/3)-restricted cuts, the minimum number of intersections (i.e., crosspoints) with tree T ∗. Suppose that the chosen cut has c crosspoints with T ∗. Then for every vertical line that lies in the middle third of W, it has at least c crosspoints with T ∗.

This means that the total length of horizontal line segments in TW = T ∗∩W is at least ca/3. It follows that the total length of TW is at least ca/3. Moving each crosspoint to its nearest portal requires adding two edges to T ∗, each of length at most b/(p + 1).

[For the middle p −2 portals, each additional edge is only of length at most b/(2(p + 1)).] So moving all c crosspoints to their respective nearest portals increases the length of the tree by at most 2cb (p + 1) ≤ 2ca (p + 1) ≤6 p · ca ≤6 p · length(TW ). We note that the union of TW over all windows at level i of the (1/3, 2/3)-partition is just T ∗, and so  W∈level i length(TW ) = length(T ∗).

Thus, the total length increase resulting from moving crosspoints to portals on all windows at level i is at most (6/p) · length(T ∗). □ Theorem 5.18 The minimum (1/3, 2/3)-guillotine rectilinear Steiner tree using p- portals, for some p = O((log n)/ε), is a (1 + ε)-approximation for RSMT. More- over, this tree can be computed in time nO(1/ε).

Proof. Suppose that the binary tree structure of a (1/3, 2/3)-partition has d logn levels for some constant d > 0. Then the total length increase that resulted from moving crosspoints to portals on all windows of the partition is at most Guillotine Cut 5.5 Quadtree Partition and Patching d logn · 6 p · length(T ∗) ≤ε · length(T ∗) if we choose p = ⌈6d log n/ε⌉.

J. Birge (University of Chicago) C.A. Floudas (Princeton University) F. Giannessi (University of Pisa) H.D. Sherali (Virginia Polytechnic and State University) T. Terlaky (McMaster University) Y. Ye (Stanford University) Aims and Scope Optimization has been expanding in all directions at an astonishing rate during the last few decades. New algorithmic and theoretical techniques have been developed, the diffusion into other disciplines has proceeded at a rapid pace, and our knowledge of all aspects of the field has grown even more profound.

At the same time, one of the most striking trends in opti- mization is the constantly increasing emphasis on the interdisciplinary na- ture of the field. Optimization has been a basic tool in all areas of applied mathematics, engineering, medicine, economics, and other sciences. The series Springer Optimization and Its Applications publishes under- graduate and graduate textbooks, monographs and state-of-the-art exposi- tory work that focus on algorithms for solving optimization problems and also study applications involving such problems.

Some of the topics covered include nonlinear optimization (convex and nonconvex), network flow prob- lems, stochastic optimization, optimal control, discrete optimization, multi- objective programming, description of software packages, approximation techniques and heuristic approaches. For further volumes: http://www.springer.com/series/7393 Ding-Zhu Du • Ker-I Ko Design and Analysis of Approximation Algorithms Xiaodong Hu • Ding-Zhu Du Ker-I Ko Department of Computer Science Department of Computer Science University of Texas at Dallas State University of New York at Stony Brook Richardson, TX 75080 Stony Brook, NY 11794 USA USA [email protected] [email protected] Xiaodong Hu Institute of Applied Mathematics Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190 China [email protected] ISSN 1931-6828 ISBN 978-1-4614-1700-2 e-ISBN 978-1-4614-1701-9 DOI 10.1007/978-1-4614-1701-9 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: ¤ Springer Science+Business Media, LLC 2012 All rights reserved.

This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer soft- ware, or by similar or dissimilar methodology now known or hereafter developed is forbidden.

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: e3e120c8d103651d
• File Extension: .pdf
• File Size: 3,460,996 bytes (3.301 MB)
• Title: –
• Author: Unknown
• ISBN: 9781461417002, 9781461417019
• Pages: 451
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 868.58 minutes
• Total Words: 173,715
• Total Characters: 911,239
• Average Words per Page: 385.18
• Average Characters per Page: 2020.49

Most Frequent Words

set (921), problem (845), algorithm (842), approximation (724), let (664), vertex (577), tree (510), graph (505), following (480), two (460), connected (448), minimum (447), solution (421), function (410), partition (389), length (379), vertices (370), steiner (367), cut (364), see (351), edge (348), proof (325), time (321), opt (314), note (307), number (304), lemma (298), given (294), also (287), feasible (284), ratio (269), one (267), input (265), algorithms (263), optimal (263), linear (262), find (261), greedy (259), consider (259), show (257), theorem (251), edges (250), total (246), programming (239), line (239), points (232), follows (231), problems (224), program (224), thus (221), polynomial-time (216), figure (216), dominating (214), since (213), size (212), therefore (209), cover (207), subset (200), every (200), weight (193), independent (191), point (187), case (184), performance (183), rounding (178), maximum (177), value (176), denote (175), new (174), disk (172), integer (167), assume (167), now (165), semidefinite (165), first (159), cost (158), suppose (157), least (157), contains (154), sets (151), instance (149), between (148), guillotine (148), max (146), path (145), segment (143), design (142), get (136), unit (135), define (134), mst (132), use (131), rectilinear (131), spanning (130), boundary (129), method (127), polynomial (123), cell (116), min (116), condition (115).

PDF Download