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:
APPROX
* 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
RANDOM
* 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.
Electronic submissions are solicited. Submission
instructions are available at
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
USA
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
USA
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.
Submission Deadline: 17:00pm (PDT), April 12th, 2004
Notification: May 26th, 2004
Camera ready: June 15th, 2004
APPROX
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
RANDOM
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
Klaus Jansen, U. of Kiel (E-mail:
kj@informatik.uni-kiel.de)
José Rolim, U. of Geneva (E-mail: rolim@cui.unige.ch)
APPROX
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
RANDOM
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