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, sub-linear 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, error-correcting codes, average-case analysis, property testing, computational learning theory, and other applications of approximation and randomness. This volume presents the refereed proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 11th International Workshop on Randomization and Computation. The papers cover design and analysis of approximation algorithms, hardness of approximation, small space and data streaming algorithms, sub-linear time algorithms, embeddings and metric space methods, and much more. Contributed Talks of APPROX Approximation Algorithms and Hardness for Domination with Propagation 1 Ashkan Aazami and Michael D. Stilp A Knapsack Secretary Problem with Applications 16 Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem 29 Jaroslaw Byrka Improved Approximation Algorithms for the Spanning Star Forest Problem 44 Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, and Gyanit Singh Packing and Covering ?-Hyperbolic Spaces by Balls 59 Victor Chepoi and Bertrand Estelion Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems 74 Ilias Diakonikolas and Mihalis Yannakakis Two Randomized Mechanisms for Combinatorial Auctions 89 Shahar Dobzinski Improved Approximation Ratios for Traveling Salespemon Tours and Paths in Directed Graphs 104 Uriel Feige and Mohit Singh Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows 119 Greg N. Frederickson and Barry Wittman Stochastic Steiner Tree with Non-uniform Inflation 134 Anuparn Gupta, Mohammad Taghi Hajiaghayi, and Amit Kumar On the Approximation Resistance of a Random Predicate 149 Johan H ad Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to 1 Embeddability of Negative Type Metrics 164 Harried Hatami, Avner Mogen, and Evangelos Markakis Optimal Resource Augmentations for Online Knapsack 180 Kazuo Iwama and Guochuan Zhang Soft Edge Coloring 189 Chadi Kari, Yoo-Ah Kim, Seungjoon Lee, Alexander Russell, and Minho Shin Approximation Algorithms for the Max-Min Allocation Problem 204 Subhash Khot and Ashok Kumar Ponnuswami Hardness of Embedding Metric Spaces of Equal Size 218 Subhash Khot and Rishi Saket Coarse Differentiation and Multi-flows in Planar Graphs 228 James R. Lee and Prasad Raghavendra Maximum Gradient Embeddings and Monotone Clustering 242 Manor Mendel and Assaf Naor Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems 257 Viswanath Nagarajan and R. Ravi Encouraging Cooperation in Sharing Supermodular Costs 2711 Andreas S. Schulz and Nelson A. Uhan Almost Exact Matchirtgs 286 Raphael Yuster Contributed Talks of RANDOM On Approximating the A verage Distance Between Points 296 Kfir Barham, Oded Goldreich, and Adi Shraibman On Locally Decodable Codes, Self-correctable Codes, and f-Private PIR 311 Omer Barkol, Yuval Ishai, and Enav Weinreb A Sequential Algorithm for Generating Random Graphs 326 Mohscre Bayati, Jeong Han Kim, and Amin Saberi Local Limit Theorems for the Giant Component of Random Hypergraphs 341 Michael Behrisch, Amin Coja-Oghlan, and Aliligun Kang Derandomization of Euclidean Random Walks 353 Ilia Binder and Mark Braverman High Entropy Random Selection Protocols 366 Harry Buhrman, Matthias Christandl, Michal Kouck , Zvi Lotker, Boaz Patt-Shamir, and Nikolai Vereshchagin Testing st-Connectivity 380 Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, and Ilan Newman Properly 2-Colouring Linear Hypergraphs 395 Arkadev Chattopadhyay and Bruce A. Reed Random Subsets of the Interval and P2P Protocols 409 Jacek Cichon, Marek Klonowski, Lukasz Krzywiecki, Bartlomiej R zanski, and Pawel Zielinski The Cover Time of Random Digraphs 422 Colin Cooper and Alan Frieze Eigenvectors of Random Graphs: Nodal Domains 436 Yael Dekel, James R. Lee, and Nathan Linial Lower Bounds for Swapping Arthur and Merlin 449 Scott Diehl Lower Bounds for Testing Forbidden Induced Substructures in Bipartite-Graph-Like Combinatorial Objects 464 Eldar Fischer and Eyal Rozenberg On Estimating Frequency Moments of Data Streams 479 Sumit Ganguly and Graham Cormode Distribution-Free Testing Lower Bounds for Basic Boolean Functions 494 Dana Glasner and Rocco A. Servedio On the Randomness Complexity of Property Testing 509 Oded Goldreich and Or Sheffet On the Benefits of Adaptivity in Property Testing of Dense Graphs 525 Mira Gonen and Dana Ron Slow Mixing of Markov Chains Using Fault Lines and Fat Contours 540 Sam Greenberg and Dana Randall Better Binary List-Decodable Codes Via Multilevel Concatenation 554 Venkatesan Guruswami and Atri Rudra Worst-Case to Average-Case Reductions Revisited 569 Dan Gutfreund and Amnon Ta-Shma On Finding Frequent Elements in a Data Stream 584 Ravi Kumar and Rina Panigrahy Implementing Huge Sparse Random Graphs 596 Moni Naor and Asaf Nussboim Sublinear Algorithms for Approximating String Compressibility 609 Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, and Adam Smith Author Index 625