【图书简介】 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.-读书网|DuShu.com
【本书目录】 Invited Talks On Nontrivial Approximation of CSPs Analysis of Algorithms on the Cores of Random Graphs Conrtibured Talks of APPROX Constant-Factor Approximation for Minimum-Weight(Connected) Dominating Sets in unit Disk Graphs Approximating Precedence-Constrained Single Machine Scheduling by Coloring Minimizing Setup and Beam-On Times in Radiation Therapy On the Valur of Preemption in Scheduling An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs Tight Resrlts on Minimum Entropy Set Cover A Tight Lower Bound for the Steiner Point Removal Prlblem on Trees Single-Source Stochastic Routing An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem Online Algorithms to Minimize Resource Reallocations and Network Communication Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs Combinatorial Algorithms for Data to Minimize Average Completion Time LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees Improved Algorithms for Data Migration Approximation Algorithms for Graph Homomorphism Problems Improved Approximation Algorithm for the One-Warehouse Hardmess of Preemptive Finite Capacity Dial-a-Ride Minimum Vehicle Routing with a Common Deadline Stochastic Combinatorial Optimization with Controllable Risk Aversion Level Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems …… Contributed Talks of RANDOM Author Index
【图书简介】
【购买本书】
