[Annotatie]: This book constitutes the joint refereed proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and the 10th International Workshop on Randomization and Computation, RANDOM 2006, held in Barcelona, Spain, in August 2006. The 44 revised full papers presented were carefully reviewed and selected from 105 submissions. Among the topics covered are design and analysis of approximation algorithms, hardness of approximation problems, small spaces and data streaming algorithms, sub-linear time algorithms, embeddings and metric space methods, mathematical programming methods, coloring and partitioning, cuts and connectivity, game theory, network design and routing, packing and covering, scheduling, design and analysis of randomized algorithms, randomized complexity theory, pseudorandomness, derandomization, random combinatorial structures, Markov chains, prohabalistic proof systems, error-correcting codes, etc. [Inhoudsopgave]: Invited TalksOn Nontrivial Approximation of CSPs1(1)Johan H adAnalysis of Algorithms on the Cores of Random Graphs2(1)Nick WormaldContributed Talks of APPROXConstant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs3(12)Christoph Amb hl, Thomas Erlebach, Mat Mihal' Marc NunkesserApproximating Precedence-Constrained Single Machine Scheduling by Coloring15(12)Christoph Amb hl, Monaldo Mastrolilli, Ola SvenssonMinimizing Setup and Beam-On Times in Radiation Therapy27(12)Nikhil Bansal, Don Coppersmith, Baruch SchieberOn the Value of Preemption in Scheduling39(10)Yair Bartal, Stefano Leonardi, Gil Shallom, Rene SittersAn Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs49(12)Benjamin E. Birnbaum, Kenneth J. GoldmanTight Results on Minimum Entropy Set Cover61(9)Jean Cardinal, Samuel Fiorini, Gwena JoretA Tight Lower Bound for the Steiner Point Removal Problem on Trees70(12)T.-H. Hubert Chan, Donglin Xia, Goran Konjevod, Andrea RichaSingle-Source Stochastic Routing82(13)Shuchi Chawla, Tim RoughgardenAn O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem95(9)Chandra Chekuri, Martin P /TD>Online Algorithms to Minimize Resource Reallocations and Network104(12)Sashka Davis, Jeff Edmonds, Russell ImpagliazzoWeighted Sum Coloring in Batch Scheduling of Conflicting Jobs116(12)Leah Epstein, Magn s M. Halld rsson, Asaf Levin, Hadas ShachnaiCombinatorial Algorithms for Data Migration to Minimize Average Completion Time128(12)Rajiv Gandhi, Juli MestreLP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times140(12)Alexander Grigoriev, Maxim Sviridenko, Marc UetzApproximating Buy-at-Bulk and Shallow-Light k-Steiner Trees152(12)Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. SalavatipourImproved Algorithms for Data Migration164(12)Samir Khuller, Yoo-Ah Kim, Azarakksh MalekianApproximation Algorithms for Graph Homomorphism P
nl
en
