| Formatted contents note |
Contents<br/>Part I: Basic Methodologies<br/>1 Introduction, Overview and De.nitions Teo.lo F. Gonzalez ...... 1-1 <br/>2 Basic Methodologies and Applications Teo.lo F. Gonzalez ...... 2-1 <br/>3 Restriction Methods Teo.lo F. Gonzalez ................. 3-1 <br/>4 Greedy Methods Samir Khuller, Balaji Raghavachari, and Neal E. Young <br/>4-1 <br/>5 Recursive Greedy Methods Guy Even ................... 5-1 <br/>6 Linear Programming Yuval Rabani ..................... 6-1 <br/>7 LP Rounding and Extensions Daya Ram Gaur and Ramesh Krishna¡ <br/>murti ........................................ 7-1 <br/>8 On Analyzing Semide.nite Programming Relaxations of Complex Quadratic Optimization Problems Anthony Man-Cho So, Yinyu Ye, and Jiawei Zhang ........................................ 8-1 <br/>9 Polynomial Time Approximation Schemes Hadas Shachnai and Tami <br/>Tamir ........................................ 9-1 10 Rounding, Interval Partitioning and Separation Sartaj Sahni ..... 10-1 11 Asymptotic Polynomial Time Approximation Schemes Rajeev Motwani, <br/>Liadan O¿Callaghan, and An Zhu ....................... 11-1 12 Randomized Approximation Techniques Sotiris Nikoletseas and Paul Spi¡rakis ........................................ 12-1 <br/>13 Distributed Approximation Algorithms via LP-duality and Randomiza¡tion Devdatt Dubhashi, Fabrizio Grandoni, and Alessandro Panconesi 13-1 14 Empirical Analysis of Randomised Algorithms Holger H. Hoos and Thomas St¿<br/>utzle ....................................... 14-1 15 Reductions that Preserve Approximability Giorgio Ausiello and Vangelis Th. Paschos .................................... 15-1 16 Di.erential Ratio Approximation Giorgio Ausiello and Vangelis Th. Paschos <br/>16-1 <br/>17 Hardness of Approximation Mario Szegedy ................ 17-1<br/>Part II: Local Search, Neural Networks, and Meta-heuristics <br/>18 Local Search Roberto Solis-Oba ....................... 18-1 19 Stochastic Local Search Holger H. Hoos and Thomas St¿<br/>utzle ..... 19-1 ¿<br/>20 Very Large Neighborhood Search Ravindra K. Ahuja, Olem Ergun, James B Orlin, and Abraham P Punnen ....................... 20-1 21 Reactive Search: Machine Learning for Memory-Based Heuristics Roberto Battiti and Mauro Brunato .......................... 21-1 22 Neural Networks Bhaskar DasGupta, Derong Liu, and Hava T. Siegel-mann ........................................ 22-1 <br/>23 Principles of Tabu Search Fred Glover, Manuel Laguna, and Rafael Mart´i <br/>23-1<br/>24 Evolutionary Computation Guillermo Leguizam´<br/>on, Christian Blum, and <br/>Enrique Alba ................................... 24-1<br/>25 Simulated Annealing Emile Aarts, Jan Korst, and Wil Michiels ... 25-1<br/>26 An Introduction to Ant Colony Optimization Marco Dorigo and Krzysztof<br/>Socha ........................................ 26-1<br/>27 Memetic Algorithms Carlos Cotta and Pablo Moscato ......... 27-1<br/>Part III: Multiobjective Optimization, Sensitivity Analysis and Stability <br/>28 Approximation in Multiobjective Problems Eric Angel, Evripidis Bampis,<br/>and Laurent Gourv`es .............................. 28-1<br/>29 Stochastic Local Search Algorithms for Multiobjective Combinatorial Op-<br/>29-1<br/>timization: A Review Lu´is Paquete and Thomas St¿<br/>utzle ........ <br/>30 Sensitivity Analysis in Combinatorial Optimization David Fern´<br/>andez-<br/>Baca and Balaji Venkatachalam ........................ 30-1<br/>31 Stability of Approximation Hans-Joachim B¿<br/>ockenhauer, Juraj Hromkovic,<br/>and Sebastian Seibert .............................. 31-1<br/>Part IV: Traditional Applications <br/>32 Performance Guarantees for One Dimensional Bin Packing Edward G.<br/>32-1<br/>Co.man, Jr. and J´<br/>anos Csirik ......................... <br/>33 Variants of Classical One Dimensional Bin Packing Edward G. Co.man,<br/>Jr., <br/>J´<br/>anos Csirik, and Joseph Y-T. Leung .................. 33-1<br/>34 Variable Sized Bin Packing and Bin Covering Edward G. Co.man, Jr.,<br/>J´<br/>anos Csirik, and Joseph Y-T. Leung .................... 34-1<br/>35 Multidimensional Packing Problems Rob van Stee and Leah Epstein 36 Practical Algorithms for Two-dimensional Packing Shinji Imahori, Mut-<br/>35-1<br/>sunori Yagiura, and Hiroshi Nagamochi ................... 36-1<br/>37 A Generic Primal-Dual Approximation Algorithm for an Interval Packing<br/>and Stabbing Problem So.a Kovaleva and Frits C.R. Spieksma ... 37-1<br/>38 Approximation Algorithms for Facility Dispersion S. S. Ravi, Daniel J.<br/>Rosenkrantz, and Giri K. Tayi ......................... 38-1<br/>39 Greedy Algorithms for Metric Facility Location Problems Anthony Man-<br/>Cho So, Yinyu Ye, and Jiawei Zhang ..................... 39-1<br/>40 Prize Collecting Traveling Salesman and Related Problems Giorgio Ausiello,<br/>Vincenzo Bonifaci, Stefano Leonardi, and Alberto Marchetti-Spaccamela 40-1<br/>41 A Development and Deployment Framework for Distributed Branch and<br/>Bound Peter Cappello and Chris Coakley ................. 41-1<br/>42 Approximations for Steiner Minimum Trees Ding-Zhu Du and Weili Wu 42-1<br/>43 Practical Approximations of Steiner Trees in Uniform Orientation Metrics<br/>Andrew B. Kahng, Ion Mandoiu, and Alexander Zelikovsky ....... 43-1<br/>44 Approximation Algorithms for Imprecise Computation Tasks with 0/1<br/>Constraint Joseph Y-T. Leung ....................... 44-1<br/>45 Scheduling Malleable Tasks Klaus Jansen and Hu Zhang ....... 45-1<br/>46 Vehicle Scheduling Problems in Graphs Yoshiyuki Karuno and Hiroshi<br/>Nagamochi ..................................... 46-1<br/>47 Approximation Algorithms and Heuristics for Classical Planning Jeremy<br/>48 Generalized Assignment Problem Mutsunori Yagiura and Toshihide Ibaraki<br/>Frank and Ari Jonsson ............................. 47-1<br/>48-1<br/>49 Probabilistic Greedy Heuristics for Satis.ability Problems Rajeev Kohli<br/>and Ramesh Krishnamurti ........................... 49-1<br/>Stanley P. Y. Fung, Cao-An Wang, and Francis Y. L. Chin ....... 50-1<br/>51 Approximation Schemes for Minimum-Cost k-Connectivity Problems in<br/>Geometric Graphs Artur Czumaj and Andrzej Lingas ......... 51-1<br/>52 Dilation and Detours in Geometric Networks Joachim Gudmundsson<br/>53 The Well-Separated Pair Decomposition and Its Applications Michiel<br/>54 Minimum Edge Length Rectangular Partitions Teo.lo F. Gonzalez and<br/>55 Partitioning Finite d-Dimensional Integer Grids with Applications Silvia<br/>58 Approximating Minimum Cost Connectivity Problems Guy Kortsarz and<br/>59 Optimum Communication Spanning Trees Bang Ye Wu, Chuan Yi Tang,<br/>60 Approximation Algorithms for Multilevel Graph Partitioning Burkhard<br/>61 Hypergraph Partitioning and Clustering David A. Papa and Igor L.<br/>63 Stochastic Local Search Algorithms for the Graph Colouring Problem<br/>and Christian Knauer .............................. 52-1<br/>Smid ........................................ 53-1<br/>Si Qing Zheng ................................... 54-1<br/>Part V: Computational Geometry and Graph Ap¡plications <br/>50 Approximation Algorithms for Some Optimal 2D and 3D Triangulations <br/>Ghilezan, Jovanka Pantovi´c, and Jovisa Zuni´c ............... 55-1<br/>56 Maximum Planar Subgraph Gruia Calinescu and Cristina G. Fernandes 56-1<br/>57 Edge-Disjoint Paths and Unsplittable Flow Stavros G. Kolliopoulos . 57-1<br/>Zeev Nutov .................................... 58-1<br/>and Kun-Mao Chao ............................... 59-1<br/>Monien, Robert Preis, and Stefan Schamberger .............. 60-1<br/>Markov ....................................... 61-1<br/>62 Finding Most Vital Edges in a Graph Hong Shen ............ 62-1<br/>Marco Chiarandini, Irina Dumitrescu, and Thomas St¿<br/>utzle ....... 63-1<br/>64 On Solving the Maximum Disjoint Paths Problem with Ant Colony Op<br/>¡timization Maria J. Blesa and Christian Blum .............. 64-1<br/>Part VI: Large-Scale and Emerging Applications <br/>65 Cost-E.cient Multicast Routing in Ad Hoc and Sensor Networks Pedro <br/>M. <br/>Ruiz and Ivan Stojmenovic ......................... 65-1<br/>66 Approximation Algorithm for Clustering in Ad-hoc Networks Lan Wang<br/>67 Topology Control Problems for Wireless Ad hoc Networks Errol L. Lloyd<br/>and Stephan Olariu ............................... 66-1<br/>and S. S. Ravi ................................... 67-1<br/>Yu Wang ...................................... 68-1<br/>69 Multicast Topology Inference and Its Applications Hui Tian and Hong<br/>Shen ........................................ 69-1<br/>70 Multicast Congestion in Ring Networks SingLing Lee, RongJou Yang,<br/>and Hann-Jang Ho ................................ 70-1<br/>71 QoS Multimedia Multicast Routing Ion Mandoiu, Alex Olshevsky, and<br/>Alexander Zelikovsky .............................. 71-1<br/>72 Overlay Networks for Peer-to-Peer Networks Andr´ea W. Richa and Chris<br/>¡<br/>tian Scheideler .................................. 72-1<br/>73 Scheduling Data Broadcasts on Wireless Channels: Exact Solutions and<br/>Heuristics Alan A. Bertossi, M. Cristina Pinotti, and Romeo Rizzi . 73-1<br/>74 Combinatorial and Algorithmic Issues for Microarray Analysis Carlos<br/>Cotta, Michael A. Langston, and Pablo Moscato ............. 74-1<br/>75 Approximation Algorithms for the Primer Selection, Planted Motif Search,<br/>and Related Problems Sudha Balla, Jaime Davila, and Sanguthevar Ra¡<br/>jasekaran ...................................... 75-1<br/>76 Dynamic and Fractional Programming based Approximation Algorithms<br/>Egecioglu ..................................... 76-1<br/>77 Approximation Algorithms for the Selection of Robust Tag SNPs Yao-<br/>Ting Huang, Kui Zhang, Ting Chen, and Kun-Mao Chao ........ 77-1<br/>78 Sphere Packing and Medical Applications Danny Z. Chen and Jinhui<br/>Xu .......................................... 78-1<br/>79 Large-Scale Global Placement Jason Cong and Joseph R. Shinnerl . 79-1<br/>80 Multicommodity Flow Algorithms for Bu.ered Global Routing Christoph<br/>Albrecht, Andrew B. Kahng, Ion Mandoiu, and Alexander Zelikovsky 80-1<br/>81 Algorithmic Game Theory and Scheduling Eric Angel, Evripidis Bampis,<br/>and Fanny Pascual ................................ 81-1<br/>82 Approximate Economic Equilibrium Algorithms Xiaotie Deng and Li-<br/>Sha Huang ..................................... 82-1<br/>83 Approximation Algorithms and Algorithm Mechanism Design Xiang-<br/>Yang Li and Weizhao Wang .......................... 83-1<br/>84 Histograms, Wavelets, Streams and Approximation Sudipto Guha .. 84-1<br/>85 Digital Reputation for Virtual Communities Roberto Battiti and Anurag<br/>68 Geometrical Spanner for Wireless Ad Hoc Networks Xiang-Yang Li and <br/>¿ <br/>for Sequence Alignment with Constraints Abdullah N. Arslan and Omer <br/>Garg ........................................ 85-1<br/>86 Color Quantization Zhigang Xiang ..................... 86-1<br/>I<br/>Basic Methodologies<br/>10 Rounding, Interval Partitioning and Separation Sartaj Sahni . . . . . 10-1 11 Asymptotic Polynomial Time Approximation Schemes Rajeev Motwani, Liadan O¿Callaghan, and An Zhu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-1 12 Randomized Approximation Techniques Sotiris Nikoletseas and Paul Spirakis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12-1 <br/>13 Distributed Approximation Algorithms via LP-duality and Randomization Devdatt Dubhashi, Fabrizio Grandoni, and Alessandro Panconesi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13-1 <br/>14 Empirical Analysis of Randomised Algorithms Holger H. Hoos and Thomas St¿<br/>utzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14-1 15 Reductions that Preserve Approximability Giorgio Ausiello and Vangelis Th. Paschos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15-1 16 Di.erential Ratio Approximation Giorgio Ausiello and Vangelis Th. Paschos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16-1 17 Hardness of Approximation Mario Szegedy . . . . . . . . . . . . . . . . . . . . . . . . . . 17-1 <br/>I-1 |