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

@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
  
• Russell Impagliazzo:
  Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems. 2-5
  
• Anna R. Karlin:
  Web Search via Hub Synthesis. 6
  
• Luca Trevisan:
  Error-Correcting Codes and Pseudorandom Projections. 7-9
  
• Salil P. Vadhan:
  Order in Pseudorandomness. 10-11
  

Contributed Talks of APPROX

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

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
  
• Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe:
  On a Generalized Ruin Problem. 181-191
  
• Andreas Baltz, Tomasz Schoen, Anand Srivastav:
  On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation. 192-201
  
• Sung-woo Cho, Ashish Goel:
  Exact Sampling in Machine Scheduling Problems. 202-210
  
• Andrea E. F. Clementi, Pierluigi Crescenzi, Angelo Monti, Paolo Penna, Riccardo Silvestri:
  On Computing Ad-hoc Selective Families. 211-222
  
• Don Coppersmith:
  L Infinity Embeddings. 223-228
  
• John Dunagan, Santosh Vempala:
  On Euclidean Embeddings and Bandwidth Minimization. 229-240
  
• Lars Engebretsen:
  The Non-approximability of Non-Boolean Predicates. 241-248
  
• Adam Klivans:
  On the Derandomization of Constant Depth Circuits. 249-260
  
• Michal Parnas, Dana Ron, Ronitt Rubinfeld:
  Testing Parenthesis Languages. 261-272
  
• Michal Parnas, Dana Ron, Alex Samorodnitsky:
  Proclaiming Dictators and Juntas or Testing Boolean Formulae. 273-284
  
• Sriram V. Pemmaraju:
  Equitable Coloring Extends Chernoff-Hoeffding Bounds. 285-296