5. RANDOM / 4. APPROX 2001: Berkeley, CA, USA

Michel X. Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan (Eds.): Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18-20, 2001, Proceedings. Lecture Notes in Computer Science 2129 Springer 2001, ISBN 3-540-42470-9 BibTeX

@proceedings{DBLP:conf/random/2001,
  editor    = {Michel X. Goemans and
               Klaus Jansen and
               Jos{\'e} D. P. Rolim and
               Luca Trevisan},
  title     = {Approximation, Randomization and Combinatorial Optimization:
               Algorithms and Techniques, 4th International Workshop on Approximation
               Algorithms for Combinatorial Optimization Problems, APPROX 2001
               and 5th International Workshop on Randomization and Approximation
               Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA,
               August 18-20, 2001, Proceedings},
  booktitle = {RANDOM-APPROX},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {2129},
  year      = {2001},
  isbn      = {3-540-42470-9},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talks

Michel X. Goemans:
Using Complex Semidefinite Programming for Approximating MAX E2-LIN3. 1
Electronic Edition (Springer LINK) BibTeX
Russell Impagliazzo:
Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems. 2-5
Electronic Edition (Springer LINK) BibTeX
Anna R. Karlin:
Web Search via Hub Synthesis. 6
Electronic Edition (Springer LINK) BibTeX
Luca Trevisan:
Error-Correcting Codes and Pseudorandom Projections. 7-9
Electronic Edition (Springer LINK) BibTeX
Salil P. Vadhan:
Order in Pseudorandomness. 10-11
Electronic Edition (Springer LINK) BibTeX

Contributed Talks of APPROX

Susanne Albers, Carsten Witt:
Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows. 12-23
Electronic Edition (Springer LINK) BibTeX
Reuven Bar-Yehuda, Dror Rawitz:
On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique. 24-35
Electronic Edition (Springer LINK) BibTeX
Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Kirk Pruhs:
Online Weighted Flow Time and Deadline Scheduling. 36-47
Electronic Edition (Springer LINK) BibTeX
Piotr Berman, Junichiro Fukuyama:
An Online Algorithm for the Postman Problem with a Small Penalty. 48-54
Electronic Edition (Springer LINK) BibTeX
Adriana Felicia Bumb, Walter Kern:
A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem. 55-62
Electronic Edition (Springer LINK) BibTeX
Alberto Caprara, Hans Kellerer, Ulrich Pferschy:
Approximation Schemes for Ordered Vector Packing Problems. 63-74
Electronic Edition (Springer LINK) BibTeX
Yevgeniy Dodis, Shai Halevi:
Incremental Codes. 75-89
Electronic Edition (Springer LINK) BibTeX
Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov:
A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set. 90-101
Electronic Edition (Springer LINK) BibTeX
Rahul Garg, Vijay Kumar, Vinayaka Pandit:
Approximation Algorithms for Budget-Constrained Auctions. 102-113
Electronic Edition (Springer LINK) BibTeX
Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai:
Minimizing Average Completion of Dedicated Tasks and Interval Graphs. 114-126
Electronic Edition (Springer LINK) BibTeX
Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani:
A Greedy Facility Location Algorithm Analyzed Using Dual Fitting. 127-137
Electronic Edition (Springer LINK) BibTeX
Shiro Matuura, Tomomi Matsui:
63-Approximation Algorithm for MAX DICUT. 138-146
Electronic Edition (Springer LINK) BibTeX
Alantha Newman:
The Maximum Acyclic Subgraph Problem and Degree-3 Graphs. 147-158
Electronic Edition (Springer LINK) BibTeX
Estela Maris Rodrigues, Marie-France Sagot, Yoshiko Wakabayashi:
Some Approximation Results for the Maximum Agreement Forest Problem. 159-169
Electronic Edition (Springer LINK) BibTeX

Contributed Talks of RANDOM

Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski, Endre Szemerédi:
Near-optimum Universal Graphs for Graphs with Bounded Degrees. 170-180
Electronic Edition (Springer LINK) BibTeX
Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe:
On a Generalized Ruin Problem. 181-191
Electronic Edition (Springer LINK) BibTeX
Andreas Baltz, Tomasz Schoen, Anand Srivastav:
On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation. 192-201
Electronic Edition (Springer LINK) BibTeX
Sung-woo Cho, Ashish Goel:
Exact Sampling in Machine Scheduling Problems. 202-210
Electronic Edition (Springer LINK) BibTeX
Andrea E. F. Clementi, Pierluigi Crescenzi, Angelo Monti, Paolo Penna, Riccardo Silvestri:
On Computing Ad-hoc Selective Families. 211-222
Electronic Edition (Springer LINK) BibTeX
Don Coppersmith:
L Infinity Embeddings. 223-228
Electronic Edition (Springer LINK) BibTeX
John Dunagan, Santosh Vempala:
On Euclidean Embeddings and Bandwidth Minimization. 229-240
Electronic Edition (Springer LINK) BibTeX
Lars Engebretsen:
The Non-approximability of Non-Boolean Predicates. 241-248
Electronic Edition (Springer LINK) BibTeX
Adam Klivans:
On the Derandomization of Constant Depth Circuits. 249-260
Electronic Edition (Springer LINK) BibTeX
Michal Parnas, Dana Ron, Ronitt Rubinfeld:
Testing Parenthesis Languages. 261-272
Electronic Edition (Springer LINK) BibTeX
Michal Parnas, Dana Ron, Alex Samorodnitsky:
Proclaiming Dictators and Juntas or Testing Boolean Formulae. 273-284
Electronic Edition (Springer LINK) BibTeX
Sriram V. Pemmaraju:
Equitable Coloring Extends Chernoff-Hoeffding Bounds. 285-296
Electronic Edition (Springer LINK) BibTeX