Design and Analysis of Approximation Algorithms
When precise algorithmic solutions are difficult to compute, the use of approximation algorithms can help. Design and Analysis of Approximation Algorithms is a textbook for a graduate course in theoretical computer science taught globally in universities.
- PDF / 4,449,057 Bytes
- 450 Pages / 439.37 x 666.14 pts Page_size
- 98 Downloads / 226 Views
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 optimization is the constantly increasing emphasis on the interdisciplinary nature 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 undergraduate and graduate textbooks, monographs and state-of-the-art expository 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 problems, stochastic optimization, optimal control, discrete optimization, multiobjective 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 • Xiaodong Hu
Design and Analysis of Approximation Algorithms
Ding-Zhu Du Department of Computer Science University of Texas at Dallas Richardson, TX 75080 USA [email protected]
Ker-I Ko Department of Computer Science State University of New York at Stony Brook Stony Brook, NY 11794 USA [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: 2011942512 ¤ 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 software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Preface
An approximation algorithm is an efficient algorithm that produces solutions to an optimization problem that are guaranteed to be within a fixed ratio of the optimal solution. Instead of spending an exponential amount of time finding the optimal solution, an approximation algorithm settles for near-optimal so
Data Loading...
