Description 
1 online resource (xii, 626 pages) 
Series 
Lecture notes in computer science, 03029743 ; 4627 

Lecture notes in computer science ; 4627. 03029743

Contents 
Contributed Talks of APPROX  Approximation Algorithms and Hardness for Domination with Propagation  A Knapsack Secretary Problem with Applications  An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem  Improved Approximation Algorithms for the Spanning Star Forest Problem  Packing and Covering?Hyperbolic Spaces by Balls  Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems  Two Randomized Mechanisms for Combinatorial Auctions  Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs  Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with UnitTime Windows  Stochastic Steiner Tree with Nonuniform Inflation  On the Approximation Resistance of a Random Predicate  Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to?1 Embeddability of Negative Type Metrics  Optimal Resource Augmentations for Online Knapsack  Soft Edge Coloring  Approximation Algorithms for the MaxMin Allocation Problem  Hardness of Embedding Metric Spaces of Equal Size  Coarse Differentiation and Multiflows in Planar Graphs  Maximum Gradient Embeddings and Monotone Clustering  Polylogarithmic Approximation Algorithms for Directed Vehicle Routing Problems  Encouraging Cooperation in Sharing Supermodular Costs  Almost Exact Matchings  Contributed Talks of RANDOM  On Approximating the Average Distance Between Points  On Locally Decodable Codes, Selfcorrectable Codes, and tPrivate PIR  A Sequential Algorithm for Generating Random Graphs  Local Limit Theorems for the Giant Component of Random Hypergraphs  Derandomization of Euclidean Random Walks  High Entropy Random Selection Protocols  Testing stConnectivity  Properly 2Colouring Linear Hypergraphs  Random Subsets of the Interval and P2P Protocols  The Cover Time of Random Digraphs  Eigenvectors of Random Graphs: Nodal Domains  Lower Bounds for Swapping Arthur and Merlin  Lower bounds for testing forbidden induced substructures in bipartitegraphlike combinatorial objects  On Estimating Frequency Moments of Data Streams  DistributionFree Testing Lower Bounds for Basic Boolean Functions  On the Randomness Complexity of Property Testing  On the Benefits of Adaptivity in Property Testing of Dense Graphs  Slow Mixing of Markov Chains Using Fault Lines and Fat Contours  Better Binary ListDecodable Codes Via Multilevel Concatenation  WorstCase to AverageCase Reductions Revisited  On Finding Frequent Elements in a Data Stream  Implementing Huge Sparse Random Graphs  Sublinear Algorithms for Approximating String Compressibility 
Summary 
This book constitutes the joint refereed proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and the 11th International Workshop on Randomization and Computation, RANDOM 2007, held in Princeton, NJ, USA, in August 2007. The 44 revised full papers presented were carefully reviewed and selected from 99 submissions. Topics of interest covered by the papers are design and analysis of approximation algorithms, hardness of approximation, small space and data streaming algorithms, sublinear time algorithms, embeddings and metric space methods, mathematical programming methods, coloring and partitioning, cuts and connectivity, geometric problems, game theory and applications, network design and routing, packing and covering, scheduling, design and analysis of randomized algorithms, randomized complexity theory, pseudorandomness and derandomization, random combinatorial structures, random walks/Markov chains, expander graphs and randomness extractors, probabilistic proof systems, random projections and embeddings, errorcorrecting codes, averagecase analysis, property testing, computational learning theory, and other applications of approximation and randomness 
Notes 
International conference proceedings 
Bibliography 
Includes bibliographical references and index 
Notes 
Title from title screen (viewed Sept. 11, 2007) 
Subject 
Computer science  Statistical methods  Congresses.


Computer algorithms  Congresses.

Genre/Form 
Conference papers and proceedings.


Conference papers and proceedings.

Form 
Electronic book

Author 
Charikar, Moses.


International Workshop on Randomization and Computation (11th : 2007 : Princeton, N.J.)

LC no. 
2007932294 
ISBN 
9783540742074 

3540742077 

3540742085 

9783540742081 
