LEADER 06305nam 22007575 450 001 9910484212003321 005 20251226200234.0 010 $a3-540-38045-0 024 7 $a10.1007/11830924 035 $a(CKB)1000000000283736 035 $a(SSID)ssj0000316310 035 $a(PQKBManifestationID)11246734 035 $a(PQKBTitleCode)TC0000316310 035 $a(PQKBWorkID)10263649 035 $a(PQKB)10460261 035 $a(DE-He213)978-3-540-38045-0 035 $a(MiAaPQ)EBC4516814 035 $a(PPN)123137721 035 $a(BIP)34164221 035 $a(BIP)13592584 035 $a(EXLCZ)991000000000283736 100 $a20100301d2006 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques $e9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30, 2006, Proceedings /$fedited by Josep Diaz, Klaus Jansen, José D.P. Rolim, Uri Zwick 205 $a1st ed. 2006. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2006. 215 $a1 online resource (XII, 522 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4110 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-540-38044-2 320 $aIncludes bibliographical references and index. 327 $aInvited Talks -- On Nontrivial Approximation of CSPs -- Analysis of Algorithms on the Cores of Random Graphs -- Contributed 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 Value of Preemption in Scheduling -- An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs -- Tight Results on Minimum Entropy Set Cover -- A Tight Lower Bound for the Steiner Point Removal Problem on Trees -- Single-Source Stochastic Routing -- An O(logn) 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 Migration 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 Multi-Retailer Problem -- Hardness 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 -- Better Approximations for the Minimum Common Integer Partition Problem -- Contributed Talks of RANDOM -- On Pseudorandom Generators with Linear Stretch in NC0 -- A Fast Random Sampling Algorithm for Sparsifying Matrices -- The Effect of Boundary Conditions on Mixing Rates of Markov Chains -- Adaptive Sampling and Fast Low-Rank Matrix Approximation -- Robust Local Testability of Tensor Products of LDPC Codes -- Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods -- Dobrushin Conditions and Systematic Scan -- Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems -- Robust Mixing -- Approximating Average Parameters of Graphs -- Local Decoding and Testing for Homomorphisms -- Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy -- Randomness-Efficient Sampling Within NC 1 -- Monotone Circuits for the Majority Function -- Space Complexity vs. Query Complexity -- Consistency of Local Density Matrices Is QMA-Complete -- On Bounded Distance Decoding for General Lattices -- Threshold Functions for Asymmetric Ramsey Properties Involving Cliques -- Distance Approximation in Bounded-Degree and General Sparse Graphs -- Fractional Matching Via Balls-and-Bins -- A Randomized Solver for Linear Systems with Exponential Convergence -- Maintaining External Memory Efficient Hash Tables. 330 $aThis is 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. The book presents 44 carefully reviewed and revised full papers. Among the topics covered are design and analysis of approximation algorithms, hardness of approximation problems, small spaces and data streaming algorithms, embeddings and metric space methods, and more. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4110 606 $aSoftware engineering 606 $aAlgorithms 606 $aComputer science$xMathematics 606 $aDiscrete mathematics 606 $aNumerical analysis 606 $aSoftware Engineering 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aNumerical Analysis 615 0$aSoftware engineering. 615 0$aAlgorithms. 615 0$aComputer science$xMathematics. 615 0$aDiscrete mathematics. 615 0$aNumerical analysis. 615 14$aSoftware Engineering. 615 24$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aNumerical Analysis. 676 $a005.1 701 $aDiaz$b J$g(Josep),$f1950-$01221273 712 12$aInternational Workshop on Randomization and Computation$d(10th :$f2006 :$eBarcelona, Spain) 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484212003321 996 $aApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques$94522937 997 $aUNINA