Call For Papers

APPROX 2004 + RANDOM 2004


7th. International Workshop on
Approximation Algorithms for Combinatorial Optimization Problems


8th. International Workshop on
Randomization and Computation

22-24 August 2004
Harvard University

Submission Deadline: 20:00 EST, April 12, 2004


The 7th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems - APPROX'2004 - and the 8th. International Workshop on Randomization and Computation - RANDOM'2004 - will be colocated at Harvard University, Cambridge, on August 22-24, 2004. APPROX'2004 focuses on algorithmic and complexity aspects arising in the development of efficient approximate solutions to computationally difficult problems, while RANDOM'2004 focuses on applications of randomness to computational and combinatorial problems. RANDOM'2004 is the eighth workshop in the series after Bologna, Barcelona, Berkeley, Geneva, Berkeley again, Harvard and Princeton; APPROX'2004 is the seventh in the series after Aalborg, Berkeley, Saarbrücken, Berkeley again, Rome and Princeton.


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



  * design and analysis of approximation algorithms
  * inapproximability results
  * approximation classes
  * on-line problems
  * small space and data streaming algorithms
  * sub-linear time algorithms
  * embeddings and metric space methods in approximation
  * math progamming in approximation algorithms
  * coloring and partitioning
  * cuts and connectivity
  * geometric problems
  * network design and routing
  * packing and covering
  * scheduling
  * game theory
  * other applications


  * design and analysis of randomized algorithms
  * randomized complexity theory
  * pseudorandomness and derandomization
  * random combinatorial structures
  * random walks/Markov chains
  * expander graphs and randomness extractors
  * probabilistic proof systems
  * random projections and embeddings
  * error-correcting codes
  * average-case analysis
  * property testing
  * computational learning theory


Proceedings will be published in the Springer-Verlag series Lecture Notes in Computer Science. Previous proceedings of APPROX appeared as LNCS 1444, 1671, 1913, 2129, 2462, and 2764, while previous proceedings of RANDOM appeared as LNCS 1269, 1518, 1671, 2129, and 2483, 2764 and as Proceedings in Informatics 8.

Guidelines for Submission

Electronic submissions are solicited. Submission instructions are available at

Electronic Submissions for APPROX

Electronic Submissions for RANDOM 

The postscript must be received by 17:00pm (PDT) of April 12th for your submission to be considered. In extreme cases, contributions to APPROX may be submitted by sending 6 hard copies to:

Sanjeev Khanna

Dept. of Computer and Information Science

University of Pennsylvania

3330 Walnut St

Philadelphia, PA 19104


and contributions to RANDOM may be submitted by sending 6 hard copies to:

Dana Ron

Radcliffe Institute for Advanced Study

Harvard University

10 Garden St

Cambridge, MA 02138


Simultaneous submission to other conferences with published proceedings is not allowed.

Submissions by program committee members are allowed.

Abstract Format: Authors should submit an extended abstract (not a full paper). An abstract should start with the title of the paper, each author's name, affiliation, and e-mail address, followed by a one-paragraph summary of the results to be presented. This should then be followed by a technical exposition of the main ideas and techniques used to achieve these results, including motivation and a clear comparison with related work. The abstract should not exceed 10 single-spaced pages on letter-size paper, using reasonable margins and at least 11-point font. If the authors believe that more details are essential to substantiate the main claims of the paper, they may include a clearly marked appendix that will be read at the discretion of the program committee.

Important Dates

Submission Deadline: 17:00pm (PDT), April 12th, 2004
Notification: May 26th, 2004
Camera ready: June 15th, 2004

Program Committees


  Chandra Chekuri, Bell Laboratories
  Lisa Fleischer, Carnegie Mellon U. and IBM T.J. Watson
  Sudipto Guha, U. of Pennsylvania
  Sanjeev Khanna, U. of Pennsylvania (Chair)
  Rajmohan Rajaraman, Northeastern U.
  Tim Roughgarden, UC Berkeley
  Baruch Schieber, IBM T.J. Watson
  Martin Skutella, Max Planck Institute
  Dan Spielman, MIT
  Luca Trevisan, UC Berkeley
  Mihalis Yannakakis, Columbia U.
  Neal Young, UC Riverside


  Noga Alon, Tel Aviv U.
  Amos Beimel, Ben Gurion U.
  Peter Bro Miltersen, U. of Aarhus
  Funda Ergun, Case Western Reserve U.
  Uri Feige, Weizmann Institute
  Leslie Ann Goldberg, U. of Warwick
  Russell Impagliazzo, UC San-Diego
  Adam Kalai, Toyota Technological Institute
  Satish Rao, UC Berkeley
  Dana Ron, Tel Aviv University and Radcliffe Institute, Harvard (Chair)
  Rocco Servedio, Columbia U.
  Neal Young, UC Riverside

Workshop Chairs

Klaus Jansen, U. of Kiel (E-mail:
José Rolim, U. of Geneva (E-mail:

Steering Committee


  Susanne Albers, U. of Freiburg
  Dorit Hochbaum, UC Berkeley
  Klaus Jansen, U. of Kiel
  Samir Khuller, Maryland
  José Rolim, U. of Geneva
  Vijay Vazirani, Georgia Tech



  Josep Diaz, UPC Barcelona
  Oded Goldreich, Weizmann
  Klaus Jansen, U. of Kiel
  Michael Luby, Digital Fountain
  Christos Papadimitriou, UC Berkeley
  José Rolim, U. of Geneva
  Paul Spirakis, U. of Patras


Conference Web Page