in conjunction with


The 2nd. International Workshop on

Approximation Algorithms for Combinatorial

Optimization Problems

in conjunction with

The 3rd. International Workshop on

Randomization and Approximation Techniques in

Computer Science

8-11 August 1999

Berkeley, California

Preliminary Call for Papers


The 2nd. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems - APPROX'99 - and the 3rd. International Workshop on Randomization and Approximation Techniques in Computer Science - RANDOM'99 - will colocate at the Computer Science Department of the University of California, Berkeley on August 8-11, 1999.

APPROX'99 focuses on algorithmic and complexity aspects arising in the development of efficient approximate solutions to computationally difficult problems, while RANDOM'99 focuses on applications of randomness to computational and combinatorial problems.

RANDOM'99 is the third workshop in the series after Bologna and Barcelona; APPROX'99 is the second in the series after Aalborg.


Papers are solicited in all research areas related to randomization and approximation, including, but not limited to:

*design and analysis of randomized algorithms
* randomized complexity theory
* de-randomization techniques
* design and analysis of approximation algorithms
* complexity of approximation problems
* parallel and network algorithms
* sources of randomness
* inapproximability results
* average-case analysis
* approximation classes
* random combinatorial structures


Proceedings will be published in the Springer-Verlag series Lecture Notes in Computer Science. Previous proceedings of RANDOM appeared as LNCS 1269 and LNCS 1518 while proceedings of APPROX appeared as LNCS 1444.


Electronic submissions are solicited. A postscript file must be sent to

The postscript must be received by 11:59pm (PDT) of April 2nd for your submission to be considered. In extreme cases, contributions may be submitted by sending 6 hard copies to:

Centre Universitaire d'Informatique
University of Geneva
24 rue General Dufour
1211 Geneva 4

Your hard copy submission must be received by April 2nd in order to be considered.

Submissions should consist of: a cover page, with the author's full name, address, fax number, e-mail address, a 100-word abstract, keywords and to which workshop (APPROX or RANDOM) the paper is being submitted (for electronic submission, this page should be in the form of a separate ascii-only e-mail); an extended abstract describing original research in no more than 10 pages; an optional appendix, with more details to be read/consulted at the discretion of the Program Committee. It is expected that accepted papers will be presented at the conference. Simultaneous submission to other conferences with published proceedings is not allowed.


* Submission Deadline: 2 April
* Notification: 23 May
* Camera ready: 6 June



* Dorit Hochbaum, Berkeley, Chair
* Sanjeev Arora Princeton
* Leslie Hall John Hopkins
* Samir Khuller Maryland
* Phil Klein Brown
* Kurt Mehlhorn MPI Saarbrucken
* Joe Mitchell Stony Brook
* Seffi Naor Bell Labs and Technion
* David Peleg Weizmann
* Vijay Vazirani Georgia Tech.
* David Williamson IBM
* Gerhard Woeginger Graz


* Alistair Sinclair Berkeley, Chair
* Noga Alon Tel Aviv
* Jennifer Chayes Microsoft Research
* Monika Henzinger Compaq-SRC
* Mark Jerrum Edinburgh
* Ravi Kannan Yale
* David Karger MIT
* Valerie King Victoria
* Jon Kleinberg Cornell
* Andrzej Rucinski Poznan
* Leonard Schulman Georgia Tech
* Raimund Seidel Saarbruecken
* Joel Spencer Courant Institute
* Amnon Ta-Shma ICSI/Berkeley
* Emo Welzl ETH Zurich


* Klaus Jansen, IDSIA Lugano

* Jose Rolim, U. of Geneva


* Josep Diaz, UPC Barcelona
* Oded Goldreich, MIT and Weizmann
* Klaus Jansen, IDSIA Lugano
* Michael Luby, ICSI Berkeley
* Christos Papadimitriou, UC Berkeley
* Jose Rolim, U. of Geneva
* Paul Spirakis, U. of Patras

Further information can be found at         or