CRCnetBASE - Handbook of Approximation Algorithms and Metaheuristics

Handbook of Approximation Algorithms and Metaheuristics

Citation Information

Handbook of Approximation Algorithms and Metaheuristics

Edited by Teofilo F. Gonzalez

Chapman and Hall/CRC 2007

Print ISBN: 978-1-58488-550-4

eBook ISBN: 978-1-4200-1074-9

Table of Contents

Permalink

http://dx.doi.org/10.1201/9781420010749

Download to Citation Mgr

View Abstracts

Add to Bookshelf

Email
Access

Page

Title
Front Matter

Abstract - Hi-Res PDF (1698 KB) - PDF w/links (1699 KB)
Chapter 1. Introduction, Overview, and Notation

Abstract - Hi-Res PDF (300 KB) - PDF w/links (318 KB)
Chapter 2. Basic Methodologies and Applications

Abstract - Hi-Res PDF (386 KB) - PDF w/links (391 KB)
Chapter 3. Restriction Methods

Abstract - Hi-Res PDF (284 KB) - PDF w/links (295 KB)
Chapter 4. Greedy Methods
Samir Khuller, Balaji Raghavachari, Neal E. Young

Abstract - Hi-Res PDF (259 KB) - PDF w/links (271 KB)
Chapter 5. Recursive Greedy Methods
Guy Even

Abstract - Hi-Res PDF (311 KB) - PDF w/links (316 KB)
Chapter 6. Linear Programming
Yuval Rabani

Abstract - Hi-Res PDF (247 KB) - PDF w/links (254 KB)
Chapter 7. LP Rounding and Extensions
Ramesh Krishnamurti, Daya Ram Gaur

Abstract - Hi-Res PDF (250 KB) - PDF w/links (264 KB)
Chapter 8. On Analyzing Semidefinite Programming Relaxations of Complex Quadratic Optimization Problems
Jiawei Zhang, Yinyu Ye, Anthony Man-Cho So

Abstract - Hi-Res PDF (278 KB) - PDF w/links (284 KB)
Chapter 9. Polynomial-Time Approximation Schemes
Hadas Shachnai, Tami Tamir

Abstract - Hi-Res PDF (367 KB) - PDF w/links (378 KB)
Chapter 10. Rounding, Interval Partitioning, and Separation
Sartaj Sahni

Abstract - Hi-Res PDF (504 KB) - PDF w/links (512 KB)
Chapter 11. Asymptotic Polynomial-Time Approximation Schemes
An Zhu, Rajeev Motwani, Liadan O’Callaghan

Abstract - Hi-Res PDF (255 KB) - PDF w/links (263 KB)
Chapter 12. Randomized Approximation Techniques
Paul Spirakis, Sotiris Nikoletseas

Abstract - Hi-Res PDF (262 KB) - PDF w/links (267 KB)
Chapter 13. Distributed Approximation Algorithms via LP-Duality and Randomization
Alessandro Panconesi, Fabrizio Grandoni, Devdatt Dubhashi

Abstract - Hi-Res PDF (380 KB) - PDF w/links (396 KB)
Chapter 14. Empirical Analysis of Randomized Algorithms
Holger H. Hoos, Thomas Stutzle

Abstract - Hi-Res PDF (468 KB) - PDF w/links (482 KB)
Chapter 15. Reductions That Preserve Approximability
Giorgio Ausiello, Vangelis Th. Paschos

Abstract - Hi-Res PDF (330 KB) - PDF w/links (340 KB)
Chapter 16. Differential Ratio Approximation
Giorgio Ausiello, Vangelis Th. Paschos

Abstract - Hi-Res PDF (342 KB) - PDF w/links (361 KB)
Chapter 17. Hardness of Approximation
Mario Szegedy

Abstract - Hi-Res PDF (288 KB) - PDF w/links (299 KB)
Chapter 18. Local Search
Roberto Solis-Oba

Abstract - Hi-Res PDF (394 KB) - PDF w/links (398 KB)
Chapter 19. Stochastic Local Search
Holger H. Hoos, Thomas Stützle

Abstract - Hi-Res PDF (297 KB) - PDF w/links (312 KB)
Chapter 20. Very Large-Scale Neighborhood Search
Özlem Ergun, Abraham P. Punnen, James B. Orlin, Ravindra K. Ahuja

Abstract - Hi-Res PDF (330 KB) - PDF w/links (347 KB)
Chapter 21. Reactive Search
Mauro Brunato, Roberto Battiti

Abstract - Hi-Res PDF (385 KB) - PDF w/links (409 KB)
Chapter 22. Neural Networks
Hava T. Siegelmann, Bhaskar DasGupta, Derong Liu

Abstract - Hi-Res PDF (272 KB) - PDF w/links (283 KB)
Chapter 23. Principles of Tabu Search
Rafael Marti, Manuel Laguna, Fred Glover

Abstract - Hi-Res PDF (265 KB) - PDF w/links (270 KB)
Chapter 24. Evolutionary Computation
Guillermo Leguizamon, Enrique Alba, Christian Blum

Abstract - Hi-Res PDF (379 KB) - PDF w/links (386 KB)
Chapter 25. Simulated Annealing
Jan Korst, Emile Aarts, Wil Michiels

Abstract - Hi-Res PDF (236 KB) - PDF w/links (246 KB)
Chapter 26. Ant Colony Optimization
Marco Dorigo, Krzysztof Socha

Abstract - Hi-Res PDF (263 KB) - PDF w/links (274 KB)
Chapter 27. Memetic Algorithms
Carlos Cotta, Pablo Moscato

Abstract - Hi-Res PDF (556 KB) - PDF w/links (576 KB)
Chapter 28. Approximation in Multiobjective Problems
Laurent Gourves, Evripidis Bampis, Eric Angel

Abstract - Hi-Res PDF (359 KB) - PDF w/links (367 KB)
Chapter 29. Stochastic Local Search Algorithms for Multiobjective Combinatorial Optimization
Luis Paquete, Thomas Stutzle

Abstract - Hi-Res PDF (277 KB) - PDF w/links (293 KB)
Chapter 30. Sensitivity Analysis in Combinatorial Optimization
Balaji Venkatachalam, David Fernandez-Baca

Abstract - Hi-Res PDF (318 KB) - PDF w/links (356 KB)
Chapter 31. Stability of Approximation
Hans-Joachim Bockenhauer, Sebastian Seibert, Juraj Hromkovic

Abstract - Hi-Res PDF (288 KB) - PDF w/links (301 KB)
Chapter 32. Performance Guarantees for One-Dimensional Bin Packing
Edward G. Coffman, Janos Csirik

Abstract - Hi-Res PDF (283 KB) - PDF w/links (307 KB)
Chapter 33. Variants of Classical One-Dimensional Bin Packing
Edward G. Coffman, Joseph Y.-T. Leung, Janos Csirik

Abstract - Hi-Res PDF (237 KB) - PDF w/links (250 KB)
Chapter 34. Variable-Sized Bin Packing and Bin Covering
Edward G. Coffman, Joseph Y.-T. Leung, Janos Csirik

Abstract - Hi-Res PDF (217 KB) - PDF w/links (231 KB)
Chapter 35. Multidimensional Packing Problems
Leah Epstein, Rob van Stee

Abstract - Hi-Res PDF (518 KB) - PDF w/links (399 KB)
Chapter 36. Practical Algorithms for Two-Dimensional Packing
Mutsunori Yagiura, Hiroshi Nagamochi, Shinji Imahori

Abstract - Hi-Res PDF (320 KB) - PDF w/links (337 KB)
Chapter 37. A Generic Primal-Dual Approximation Algorithm for an Interval Packing and Stabbing Problem
Frits C. R. Spieksma, Sofia Kovaleva

Abstract - Hi-Res PDF (326 KB) - PDF w/links (332 KB)
Chapter 38. Approximation Algorithms for Facility Dispersion
Daniel J. Rosenkrantz, S. S. Ravi, Giri K. Tayi

Abstract - Hi-Res PDF (338 KB) - PDF w/links (354 KB)
Chapter 39. Greedy Algorithms for Metric Facility Location Problems
Jiawei Zhang, Yinyu Ye, Anthony Man-Cho So

Abstract - Hi-Res PDF (230 KB) - PDF w/links (240 KB)
Chapter 40. Prize-Collecting Traveling Salesman and Related Problems
Alberto Marchetti-Spaccamela, Vincenzo Bonifaci, Stefano Leonardi, Giorgio Ausiello

Abstract - Hi-Res PDF (261 KB) - PDF w/links (273 KB)
Chapter 41. A Development and Deployment Framework for Distributed Branch and Bound
Peter Cappello, Christopher James Coakley

Abstract - Hi-Res PDF (306 KB) - PDF w/links (312 KB)
Chapter 42. Approximations for Steiner Minimum Trees
Weili Wu, Ding-Zhu Du

Abstract - Hi-Res PDF (254 KB) - PDF w/links (272 KB)
Chapter 43. Practical Approximations of Steiner Trees in Uniform Orientation Metrics
Ion Mandoiu, Andrew B. Kahng, Alexander Zelikovsky

Abstract - Hi-Res PDF (310 KB) - PDF w/links (318 KB)
Chapter 44. Approximation Algorithms for Imprecise Computation Tasks with 0/1 Constraint
Joseph Y.-T. Leung

Abstract - Hi-Res PDF (230 KB) - PDF w/links (237 KB)
Chapter 45. Scheduling Malleable Tasks
Hu Zhang, Klaus Jansen

Abstract - Hi-Res PDF (306 KB) - PDF w/links (318 KB)
Chapter 46. Vehicle Scheduling Problems in Graphs
Yoshiyuki Karuno, Hiroshi Nagamochi

Abstract - Hi-Res PDF (208 KB) - PDF w/links (218 KB)
Chapter 47. Approximation Algorithms and Heuristics for Classical Planning
Jeremy Frank, Ari Jonsson

Abstract - Hi-Res PDF (519 KB) - PDF w/links (525 KB)
Chapter 48. Generalized Assignment Problem
Toshihide Ibaraki, Mutsunori Yagiura

Abstract - Hi-Res PDF (297 KB) - PDF w/links (317 KB)
Chapter 49. Probabilistic Greedy Heuristics for Satisfiability Problems
Ramesh Krishnamurti, Rajeev Kohli

Abstract - Hi-Res PDF (196 KB) - PDF w/links (203 KB)
Chapter 50. Approximation Algorithms for Some Optimal 2D and 3D Triangulations
Francis Y. L. Chin, Stanley P. Y. Fung, Cao-An Wang

Abstract - Hi-Res PDF (353 KB) - PDF w/links (374 KB)
Chapter 51. Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs
Artur Czumaj, Andrzej Lingas

Abstract - Hi-Res PDF (425 KB) - PDF w/links (434 KB)
Chapter 52. Dilation and Detours in Geometric Networks
Joachim Gudmundsson, Christian Knauer

Abstract - Hi-Res PDF (347 KB) - PDF w/links (364 KB)
Chapter 53. The Well-Separated Pair Decomposition and Its Applications
Michiel Smid

Abstract - Hi-Res PDF (262 KB) - PDF w/links (270 KB)
Chapter 54. Minimum-Edge Length Rectangular Partitions
Si Qing Zheng

Abstract - Hi-Res PDF (288 KB) - PDF w/links (291 KB)
Chapter 55. Partitioning Finite d-Dimensional Integer Grids with Applications
Silvia Ghilezan, Jovisa Zunic, Jovanka Pantovic

Abstract - Hi-Res PDF (324 KB) - PDF w/links (336 KB)
Chapter 56. Maximum Planar Subgraph
Cristina G. Fernandes, Gruia Calinescu

Abstract - Hi-Res PDF (319 KB) - PDF w/links (332 KB)
Chapter 57. Edge-Disjoint Paths and Unsplittable Flow
Stavros G. Kolliopoulos

Abstract - Hi-Res PDF (340 KB) - PDF w/links (371 KB)
Chapter 58. Approximating Minimum-Cost Connectivity Problems
Guy Kortsarz, Zeev Nutov

Abstract - Hi-Res PDF (375 KB) - PDF w/links (394 KB)
Chapter 59. Optimum Communication Spanning Trees
Chuan Yi Tang, Kun-Mao Chao, Bang Ye Wu

Abstract - Hi-Res PDF (344 KB) - PDF w/links (351 KB)
Chapter 60. Approximation Algorithms for Multilevel Graph Partitioning
Robert Preis, Burkhard Monien, Stefan Schamberger

Abstract - Hi-Res PDF (269 KB) - PDF w/links (286 KB)
Chapter 61. Hypergraph Partitioning and Clustering
David A. Papa, Igor L. Markov

Abstract - Hi-Res PDF (606 KB) - PDF w/links (616 KB)
Chapter 62. Finding Most Vital Edges in a Graph
Hong Shen

Abstract - Hi-Res PDF (292 KB) - PDF w/links (306 KB)
Chapter 63. Stochastic Local Search Algorithms for the Graph Coloring Problem
Thomas Stutzle, Irina Dumitrescu, Marco Chiarandini

Abstract - Hi-Res PDF (347 KB) - PDF w/links (360 KB)
Chapter 64. On Solving the Maximum Disjoint Paths Problem with Ant Colony Optimization
Maria J. Blesa, Christian Blum

Abstract - Hi-Res PDF (337 KB) - PDF w/links (346 KB)
Chapter 65. Cost-Efficient Multicast Routing in Ad Hoc and Sensor Networks
Ivan Stojmenovic, Pedro M. Ruiz

Abstract - Hi-Res PDF (331 KB) - PDF w/links (340 KB)
Chapter 66. Approximation Algorithm for Clustering in Ad Hoc Networks
Stephan Olariu, Lan Wang

Abstract - Hi-Res PDF (361 KB) - PDF w/links (366 KB)
Chapter 67. Topology Control Problems for Wireless Ad Hoc Networks
S. S. Ravi, Errol L. Lloyd

Abstract - Hi-Res PDF (364 KB) - PDF w/links (376 KB)
Chapter 68. Geometrical Spanner for Wireless Ad Hoc Networks
Yu Wang, Xiang-Yang Li

Abstract - Hi-Res PDF (330 KB) - PDF w/links (343 KB)
Chapter 69. Multicast Topology Inference and Its Applications
Hui Tian, Hong Shen

Abstract - Hi-Res PDF (369 KB) - PDF w/links (372 KB)
Chapter 70. Multicast Congestion in Ring Networks
SingLing Lee, RongJou Yang, Hann-Jang Ho

Abstract - Hi-Res PDF (246 KB) - PDF w/links (254 KB)
Chapter 71. QoS Multimedia Multicast Routing
Ion Măndoiu, Alex Olshevsky, Alexander Zelikovsky

Abstract - Hi-Res PDF (393 KB) - PDF w/links (403 KB)
Chapter 72. Overlay Networks for Peer-to-Peer Networks
Andrea W. Richa, Christian Scheideler

Abstract - Hi-Res PDF (340 KB) - PDF w/links (342 KB)
Chapter 73. Scheduling Data Broadcasts on Wireless Channels
Alan A. Bertossi, M. Cristina Pinotti, Romeo Rizzi

Abstract - Hi-Res PDF (340 KB) - PDF w/links (345 KB)
Chapter 74. Combinatorial and Algorithmic Issues for Microarray Analysis
Michael A. Langston, Carlos Cotta, Pablo Moscato

Abstract - Hi-Res PDF (685 KB) - PDF w/links (549 KB)
Chapter 75. Approximation Algorithms for the Primer Selection, Planted Motif Search, and Related Problems
Sudha Balla, Jaime Davila, Sanguthevar Rajasekaran

Abstract - Hi-Res PDF (366 KB) - PDF w/links (376 KB)
Chapter 76. Dynamic and Fractional Programming-Based Approximation Algorithms for Sequence Alignment with Constraints
Omer Egecioglu, Abdullah N. Arslan

Abstract - Hi-Res PDF (345 KB) - PDF w/links (351 KB)
Chapter 77. Approximation Algorithms for the Selection of Robust Tag SNPs
Kui Zhang, Kun-Mao Chao, Yao-Ting Huang, Ting Chen

Abstract - Hi-Res PDF (459 KB) - PDF w/links (468 KB)
Chapter 78. Sphere Packing and Medical Applications
Danny Z. Chen, Jinhui Xu

Abstract - Hi-Res PDF (275 KB) - PDF w/links (292 KB)
Chapter 79. Large-Scale Global Placement
Joseph R. Shinnerl, Jason Cong

Abstract - Hi-Res PDF (407 KB) - PDF w/links (401 KB)
Chapter 80. Multicommodity Flow Algorithms for Buffered Global Routing
Ion Măndoiu, Andrew B. Kahng, Christoph Albrecht, Alexander Zelikovsky

Abstract - Hi-Res PDF (428 KB) - PDF w/links (433 KB)
Chapter 81. Algorithmic Game Theory and Scheduling
Evripidis Bampis, Eric Angel, Fanny Pascual

Abstract - Hi-Res PDF (376 KB) - PDF w/links (383 KB)
Chapter 82. Approximate Economic Equilibrium Algorithms
Li-Sha Huang, Xiaotie Deng

Abstract - Hi-Res PDF (290 KB) - PDF w/links (298 KB)
Chapter 83. Approximation Algorithms and Algorithm Mechanism Design
Xiang-Yang Li, Weizhao Wang

Abstract - Hi-Res PDF (357 KB) - PDF w/links (365 KB)
Chapter 84. Histograms, Wavelets, Streams, and Approximation
Sudipto Guha

Abstract - Hi-Res PDF (350 KB) - PDF w/links (354 KB)
Chapter 85. Digital Reputation for Virtual Communities
Roberto Battiti, Anurag Garg

Abstract - Hi-Res PDF (263 KB) - PDF w/links (272 KB)
Chapter 86. Color Quantization
Zhigang Xiang

Abstract - Hi-Res PDF (736 KB) - PDF w/links (398 KB)

Chapman & Hall/CRC Computer & Information Science Series

Handbook of Approximation Algorithms and Metaheuristics