11. RANDOM / 10. APPROX 2007: Princeton, NJ, USA

Moses Charikar, Klaus Jansen, Omer Reingold, José D. P. Rolim (Eds.): Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings. Lecture Notes in Computer Science 4627 Springer 2007, ISBN 978-3-540-74207-4 BibTeX

Contributed Talks of APPROX

Ashkan Aazami, Michael D. Stilp:
Approximation Algorithms and Hardness for Domination with Propagation. 1-15
Electronic Edition (link) BibTeX
Moshe Babaioff, Nicole Immorlica, David Kempe, Robert Kleinberg:
A Knapsack Secretary Problem with Applications. 16-28
Electronic Edition (link) BibTeX
Jaroslaw Byrka:
An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. 29-43
Electronic Edition (link) BibTeX
Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh:
Improved Approximation Algorithms for the Spanning Star Forest Problem. 44-58
Electronic Edition (link) BibTeX
Victor Chepoi, Bertrand Estellon:
Packing and Covering delta -Hyperbolic Spaces by Balls. 59-73
Electronic Edition (link) BibTeX
Ilias Diakonikolas, Mihalis Yannakakis:
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems. 74-88
Electronic Edition (link) BibTeX
Shahar Dobzinski:
Two Randomized Mechanisms for Combinatorial Auctions. 89-103
Electronic Edition (link) BibTeX
Uriel Feige, Mohit Singh:
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. 104-118
Electronic Edition (link) BibTeX
Greg N. Frederickson, Barry Wittman:
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows. 119-133
Electronic Edition (link) BibTeX
Anupam Gupta, MohammadTaghi Hajiaghayi, Amit Kumar:
Stochastic Steiner Tree with Non-uniform Inflation. 134-148
Electronic Edition (link) BibTeX
Johan Håstad:
On the Approximation Resistance of a Random Predicate. 149-163
Electronic Edition (link) BibTeX
Hamed Hatami, Avner Magen, Evangelos Markakis:
Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l₁ Embeddability of Negative Type Metrics. 164-179
Electronic Edition (link) BibTeX
Kazuo Iwama, Guochuan Zhang:
Optimal Resource Augmentations for Online Knapsack. 180-188
Electronic Edition (link) BibTeX
Chadi Kari, Yoo Ah Kim, Seungjoon Lee, Alexander Russell, Minho Shin:
Soft Edge Coloring. 189-203
Electronic Edition (link) BibTeX
Subhash Khot, Ashok Kumar Ponnuswami:
Approximation Algorithms for the Max-Min Allocation Problem. 204-217
Electronic Edition (link) BibTeX
Subhash Khot, Rishi Saket:
Hardness of Embedding Metric Spaces of Equal Size. 218-227
Electronic Edition (link) BibTeX
James R. Lee, Prasad Raghavendra:
Coarse Differentiation and Multi-flows in Planar Graphs. 228-241
Electronic Edition (link) BibTeX
Manor Mendel, Assaf Naor:
Maximum Gradient Embeddings and Monotone Clustering. 242-256
Electronic Edition (link) BibTeX
Viswanath Nagarajan, R. Ravi:
Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems. 257-270
Electronic Edition (link) BibTeX
Andreas S. Schulz, Nelson A. Uhan:
Encouraging Cooperation in Sharing Supermodular Costs. 271-285
Electronic Edition (link) BibTeX
Raphael Yuster:
Almost Exact Matchings. 286-295
Electronic Edition (link) BibTeX

Contributed Talks of RANDOM

Kfir Barhum, Oded Goldreich, Adi Shraibman:
On Approximating the Average Distance Between Points. 296-310
Electronic Edition (link) BibTeX
Omer Barkol, Yuval Ishai, Enav Weinreb:
On Locally Decodable Codes, Self-correctable Codes, and t -Private PIR. 311-325
Electronic Edition (link) BibTeX
Mohsen Bayati, Jeong Han Kim, Amin Saberi:
A Sequential Algorithm for Generating Random Graphs. 326-340
Electronic Edition (link) BibTeX
Michael Behrisch, Amin Coja-Oghlan, Mihyun Kang:
Local Limit Theorems for the Giant Component of Random Hypergraphs. 341-352
Electronic Edition (link) BibTeX
Ilia Binder, Mark Braverman:
Derandomization of Euclidean Random Walks. 353-365
Electronic Edition (link) BibTeX
Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. 366-379
Electronic Edition (link) BibTeX
Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman:
Testing st -Connectivity. 380-394
Electronic Edition (link) BibTeX
Arkadev Chattopadhyay, Bruce A. Reed:
Properly 2-Colouring Linear Hypergraphs. 395-408
Electronic Edition (link) BibTeX
Jacek Cichon, Marek Klonowski, Lukasz Krzywiecki, Bartlomiej Rózanski, Pawel Zielinski:
Random Subsets of the Interval and P2P Protocols. 409-421
Electronic Edition (link) BibTeX
Colin Cooper, Alan M. Frieze:
The Cover Time of Random Digraphs. 422-435
Electronic Edition (link) BibTeX
Yael Dekel, James R. Lee, Nathan Linial:
Eigenvectors of Random Graphs: Nodal Domains. 436-448
Electronic Edition (link) BibTeX
Scott Diehl:
Lower Bounds for Swapping Arthur and Merlin. 449-463
Electronic Edition (link) BibTeX
Eldar Fischer, Eyal Rozenberg:
Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects. 464-478
Electronic Edition (link) BibTeX
Sumit Ganguly, Graham Cormode:
On Estimating Frequency Moments of Data Streams. 479-493
Electronic Edition (link) BibTeX
Dana Glasner, Rocco A. Servedio:
Distribution-Free Testing Lower Bounds for Basic Boolean Functions. 494-508
Electronic Edition (link) BibTeX
Oded Goldreich, Or Sheffet:
On the Randomness Complexity of Property Testing. 509-524
Electronic Edition (link) BibTeX
Mira Gonen, Dana Ron:
On the Benefits of Adaptivity in Property Testing of Dense Graphs. 525-539
Electronic Edition (link) BibTeX
Sam Greenberg, Dana Randall:
Slow Mixing of Markov Chains Using Fault Lines and Fat Contours. 540-553
Electronic Edition (link) BibTeX
Venkatesan Guruswami, Atri Rudra:
Better Binary List-Decodable Codes Via Multilevel Concatenation. 554-568
Electronic Edition (link) BibTeX
Dan Gutfreund, Amnon Ta-Shma:
Worst-Case to Average-Case Reductions Revisited. 569-583
Electronic Edition (link) BibTeX
Ravi Kumar, Rina Panigrahy:
On Finding Frequent Elements in a Data Stream. 584-595
Electronic Edition (link) BibTeX
Moni Naor, Asaf Nussboim:
Implementing Huge Sparse Random Graphs. 596-608
Electronic Edition (link) BibTeX
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam Smith:
Sublinear Algorithms for Approximating String Compressibility. 609-623
Electronic Edition (link) BibTeX