LEADER 08480nam 22008775 450 001 9910484414603321 005 20251226202408.0 010 $a3-642-03685-6 024 7 $a10.1007/978-3-642-03685-9 035 $a(CKB)1000000000772851 035 $a(SSID)ssj0000316312 035 $a(PQKBManifestationID)11285835 035 $a(PQKBTitleCode)TC0000316312 035 $a(PQKBWorkID)10263833 035 $a(PQKB)11306519 035 $a(DE-He213)978-3-642-03685-9 035 $a(MiAaPQ)EBC3064459 035 $a(PPN)139951024 035 $a(BIP)27391534 035 $a(EXLCZ)991000000000772851 100 $a20100301d2009 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques $e12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August, 21-23, 2009, Proceedings /$fedited by Irit Dinur, Klaus Jansen, Seffi Naor, José Rolim 205 $a1st ed. 2009. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2009. 215 $a1 online resource (XII, 742 p. 41 illus.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5687 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-642-03684-8 320 $aIncludes bibliographical references and index. 327 $aContributed Talks of APPROX -- Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs -- Adaptive Sampling for k-Means Clustering -- Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs -- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs -- Truthful Mechanisms via Greedy Iterative Packing -- Resource Minimization Job Scheduling -- The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders -- New Hardness Results for Diophantine Approximation -- PASS Approximation -- Optimal Sherali-Adams Gaps from Pairwise Independence -- An Approximation Scheme for Terrain Guarding -- Scheduling with Outliers -- Improved Inapproximability Results for Maximum k-Colorable Subgraph -- Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems -- On the Optimality of Gluing over Scales -- On Hardness of Pricing Items for Single-Minded Bidders -- Real-Time Message Routing and Scheduling -- Approximating Some Network Design Problems with Node Costs -- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties -- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy -- Minimizing Average Shortest Path Distances via Shortcut Edge Addition -- Approximating Node-Connectivity Augmentation Problems -- A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem -- Approximation Algorithms for Domatic Partitions of Unit Disk Graphs -- On the Complexity of the Asymmetric VPN Problem -- Contributed Talks of RANDOM -- Deterministic Approximation Algorithms for the Nearest Codeword Problem -- Strong Parallel Repetition Theorem for Free Projection Games -- Random Low Degree Polynomials are Hard to Approximate -- Composition of Semi-LTCs by Two-Wise Tensor Products -- On the Security of Goldreich?s One-Way Function -- Random Tensors and Planted Cliques -- Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry -- Average-Case Analyses of Vickrey Costs -- A Hypergraph Dictatorship Test with Perfect Completeness -- Extractors Using Hardness Amplification -- How Well Do Random Walks Parallelize? -- An Analysis of Random-Walk Cuckoo Hashing -- Hierarchy Theorems for Property Testing -- Algorithmic Aspects of Property Testing in the Dense Graphs Model -- Succinct Representation of Codes with Applications to Testing -- Efficient Quantum Tensor Product Expanders and k-Designs -- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND -- Pseudorandom Generators and Typically-Correct Derandomization -- Baum?s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions -- Tolerant Linearity Testing and Locally Testable Codes -- Pseudorandom Bit Generators That Fool Modular Sums -- The Glauber Dynamics for Colourings of Bounded Degree Trees -- Testing ±1-weight halfspace -- Small-Bias Spaces for Group Products -- Small Clique Detection and Approximate Nash Equilibria -- Testing Computability by Width Two OBDDs -- Improved Polynomial Identity Testing for Read-Once Formulas -- Smooth Analysis of the Condition Number and the Least Singular Value. 330 $aThis volume contains the papers presented at the 12th International Wo- shop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009) and the 13th International Workshop on Randomization and Computation (RANDOM 2009), which took place concurrently at the HP - ditorium in UC Berkeley, USA, during August 21-23, 2009. APPROX focuses on algorithmic and complexity issues surrounding the development of e'cient approximate solutions to computationally di'cult problems, and was the 12th in the series after Aalborg (1998), Berkeley (1999), Saarbru ¨cken (2000), Ber- ley (2001), Rome (2002), Princeton (2003), Cambridge (2004), Berkeley (2005), Barcelona (2006), Princeton (2007), and Boston (2008). RANDOM is concerned with applications of randomness to computational and combinatorial problems, and was the 13th workshop in the series following Bologna (1997), Barcelona (1998),Berkeley(1999),Geneva(2000),Berkeley(2001),Harvard(2002),Prin- ton (2003), Cambridge (2004), Berkeley (2005), Barcelona (2006), Princeton (2007), and Boston (2008). Topics of interest for APPROX and RANDOM are: design and analysis of approximation algorithms, hardness of approximation, small space algorithms, sub-linear time algorithms, streaming algorithms, embeddings and metric space methods,mathematicalprogrammingmethods,combinatorialproblemsingraphs andnetworks,gametheory,markets,andeconomicapplications,geometricpr- lems, packing, covering, scheduling, approximate learning, design and analysis of online algorithms, randomized complexity theory, pseudorandomness and - randomization,randomcombinatorialstructures, randomwalks/Markovchains, expander graphs and randomness extractors, probabilistic proof systems, err- correctingcodes,average-caseanalysis,propertytesting,computationallearning theory, and other applications of approximation and randomness. The volume contains 25 contributed papers, selected by the APPROX Program Committee out of 56 submissions, and 28 contributed papers, selected by the RANDOM Program Committee out of 57 submissions. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v5687 606 $aComputer programming 606 $aAlgorithms 606 $aComputer science$xMathematics 606 $aDiscrete mathematics 606 $aNumerical analysis 606 $aMathematical statistics 606 $aProgramming Techniques 606 $aAlgorithms 606 $aDiscrete Mathematics in Computer Science 606 $aNumerical Analysis 606 $aSymbolic and Algebraic Manipulation 606 $aProbability and Statistics in Computer Science 615 0$aComputer programming. 615 0$aAlgorithms. 615 0$aComputer science$xMathematics. 615 0$aDiscrete mathematics. 615 0$aNumerical analysis. 615 0$aMathematical statistics. 615 14$aProgramming Techniques. 615 24$aAlgorithms. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aNumerical Analysis. 615 24$aSymbolic and Algebraic Manipulation. 615 24$aProbability and Statistics in Computer Science. 676 $a005.11 686 $aDAT 517f$2stub 686 $aDAT 537f$2stub 686 $aMAT 410f$2stub 686 $aMAT 913f$2stub 686 $aSS 4800$2rvk 701 $aDinur$b Irit$01757865 712 12$aInternational Workshop on Randomization and Computation$d(13th :$f2009 :$eBerkeley, Calif.) 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910484414603321 996 $aApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques$94522020 997 $aUNINA