{"id":258502,"date":"2026-07-13T16:19:15","date_gmt":"2026-07-13T13:19:15","guid":{"rendered":"https:\/\/1kitap1.com\/en\/design-and-analysis-of-approximation-algorithms-ding-zhu-du\/"},"modified":"2026-07-13T16:19:15","modified_gmt":"2026-07-13T13:19:15","slug":"design-and-analysis-of-approximation-algorithms-ding-zhu-du","status":"publish","type":"post","link":"https:\/\/1kitap1.com\/en\/design-and-analysis-of-approximation-algorithms-ding-zhu-du\/","title":{"rendered":"Design And Analysis Of Approximation Algorithms – Ding – Zhu Du"},"content":{"rendered":"
\"<\/figure>\n

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 \u2217. Suppose that the chosen cut has c crosspoints with T \u2217. Then for every vertical line that lies in the middle third of W, it has at least c crosspoints with T \u2217.<\/p>\n

This means that the total length of horizontal line segments in TW = T \u2217\u2229W 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 \u2217, each of length at most b\/(p + 1).<\/p>\n

[For the middle p \u22122 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) \u2264 2ca (p + 1) \u22646 p \u00b7 ca \u22646 p \u00b7 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 \u2217, and so \u0004 W\u2208level i length(TW ) = length(T \u2217).<\/p>\n

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

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 \u00b7 6 p \u00b7 length(T \u2217) \u2264\u03b5 \u00b7 length(T \u2217) if we choose p = \u23086d log n\/\u03b5\u2309.<\/p>\n

\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 \ufb01eld has grown even more profound.<\/p>\n

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 \ufb01eld. 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.<\/p>\n

Some of the topics covered include nonlinear optimization (convex and nonconvex), network \ufb02ow 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 \u2022 Ker-I Ko Design and Analysis of Approximation Algorithms Xiaodong Hu \u2022 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 dzdu@utdallas.edu keriko@cs.sunysb.edu Xiaodong Hu Institute of Applied Mathematics Academy of Mathematics and Systems Science Chinese Academy of Sciences Beijing 100190 China xdhu@amss.ac.cn 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: \u00a4 Springer Science+Business Media, LLC 2012 All rights reserved.<\/p>\n

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.<\/p>\n<\/blockquote>\n

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.<\/em><\/p>\n

\n
\n

Table of Contents<\/p>\nToggle<\/span><\/path><\/svg><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n