9. RANDOM / 8. APPROX 2005: Berkeley, CA, USA

Chandra Chekuri, Klaus Jansen, José D. P. Rolim, Luca Trevisan (Eds.): Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings. Lecture Notes in Computer Science 3624 Springer 2005, ISBN 3-540-28239-4 BibTeX

Contributed Talks of APPROX

Stanislav Angelov, Sanjeev Khanna, Keshav Kunal:
The Network as a Storage Device: Dynamic Routing with Bounded Buffers. 1-13
Electronic Edition (link) BibTeX
Adi Avidor, Uri Zwick:
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT. 14-25
Electronic Edition (link) BibTeX
Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar:
What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs. 26-39
Electronic Edition (link) BibTeX
Victor Chepoi, Karim Nouioua, Yann Vaxès:
A Rounding Algorithm for Approximating Minimum Manhattan Networks. 40-51
Electronic Edition (link) BibTeX
Joseph Cheriyan, Mohammad R. Salavatipour:
Packing Element-Disjoint Steiner Trees. 52-61
Electronic Edition (link) BibTeX
Uriel Feige, Kunal Talwar:
Approximating the Bandwidth of Caterpillars. 62-73
Electronic Edition (link) BibTeX
Anupam Gupta, Amit Kumar:
Where's the Winner? Max-Finding and Sorting with Metric Costs. 74-85
Electronic Edition (link) BibTeX
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha:
What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization. 86-98
Electronic Edition (link) BibTeX
Venkatesan Guruswami, Luca Trevisan:
The Complexity of Making Unique Choices: Approximating 1-in- k SAT. 99-110
Electronic Edition (link) BibTeX
Alexander Hall, Christos H. Papadimitriou:
Approximating the Distortion. 111-122
Electronic Edition (link) BibTeX
Boulos Harb, Sampath Kannan, Andrew McGregor:
Approximating the Best-Fit Tree Under L_p Norms. 123-133
Electronic Edition (link) BibTeX
Gustav Hast:
Beating a Random Assignment. 134-145
Electronic Edition (link) BibTeX
V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan:
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints. 146-157
Electronic Edition (link) BibTeX
Jens Maßberg, Jens Vygen:
Approximation Algorithms for Network Design and Facility Location with Service Capacities. 158-169
Electronic Edition (link) BibTeX
Andrew McGregor:
Finding Graph Matchings in Data Streams. 170-181
Electronic Edition (link) BibTeX
Julián Mestre:
A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses. 182-191
Electronic Edition (link) BibTeX
Shlomo Moran, Sagi Snir:
Efficient Approximation of Convex Recolorings. 192-208
Electronic Edition (link) BibTeX
Viswanath Nagarajan, R. Ravi:
Approximation Algorithms for Requirement Cut on Graphs. 209-220
Electronic Edition (link) BibTeX
Jan Remy, Angelika Steger:
Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems. 221-232
Electronic Edition (link) BibTeX
Iannis Tourlakis:
Towards Optimal Integrality Gaps for Hypergraph Vertex Cover in the Lovász-Schrijver Hierarchy. 233-244
Electronic Edition (link) BibTeX

Contributed Talks of RANDOM

Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan:
Bounds for Error Reduction with Few Quantum Queries. 245-256
Electronic Edition (link) BibTeX
Moses Charikar, Chandra Chekuri, Martin Pál:
Sampling Bounds for Stochastic Optimization. 257-269
Electronic Edition (link) BibTeX
Zeev Dvir, Amir Shpilka:
An Improved Analysis of Mergers. 270-281
Electronic Edition (link) BibTeX
Uriel Feige, Eran Ofek:
Finding a Maximum Independent Set in a Sparse Random Graph. 282-293
Electronic Edition (link) BibTeX
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma:
On the Error Parameter of Dispersers. 294-305
Electronic Edition (link) BibTeX
Venkatesan Guruswami, Atri Rudra:
Tolerant Locally Testable Codes. 306-317
Electronic Edition (link) BibTeX
Venkatesan Guruswami, Salil P. Vadhan:
A Lower Bound on List Size for List Decoding. 318-329
Electronic Edition (link) BibTeX
Shirley Halevy, Eyal Kushilevitz:
A Lower Bound for Distribution-Free Monotonicity Testing. 330-341
Electronic Edition (link) BibTeX
Jeffrey C. Jackson, Rocco A. Servedio:
On Learning Random DNF Formulas Under the Uniform Distribution. 342-353
Electronic Edition (link) BibTeX
Eyal Kaplan, Moni Naor, Omer Reingold:
Derandomized Constructions of k-Wise (Almost) Independent Permutations. 354-365
Electronic Edition (link) BibTeX
Oded Lachish, Ilan Newman:
Testing Periodicity. 366-377
Electronic Edition (link) BibTeX
Vadim Lyubashevsky:
The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem. 378-389
Electronic Edition (link) BibTeX
Martin Marciniszyn, Reto Spöhel, Angelika Steger:
The Online Clique Avoidance Game on Random Graphs. 390-401
Electronic Edition (link) BibTeX
Rémi Monasson:
A Generating Function Method for the Average-Case Analysis of DPLL. 402-413
Electronic Edition (link) BibTeX
Cristopher Moore, Gabriel Istrate, Demetrios D. Demopoulos, Moshe Y. Vardi:
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas. 414-425
Electronic Edition (link) BibTeX
Dana Randall, Peter Winkler:
Mixing Points on a Circle. 426-435
Electronic Edition (link) BibTeX
Eyal Rozenman, Salil P. Vadhan:
Derandomized Squaring of Graphs. 436-447
Electronic Edition (link) BibTeX
Dekel Tsur:
Tight Bounds for String Reconstruction Using Substring Queries. 448-459
Electronic Edition (link) BibTeX
Christopher Umans:
Reconstructive Dispersers and Hitting Set Generators. 460-471
Electronic Edition (link) BibTeX
Paul Valiant:
The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. 472-481
Electronic Edition (link) BibTeX
Raphael Yuster:
Fractional Decompositions of Dense Hypergraphs. 482-493
Electronic Edition (link) BibTeX