7th. International Workshop on
Approximation Algorithms for Combinatorial Optimization Problems
and
8th. International Workshop on
Randomization and Computation
22-24 August 2004
Harvard University
Submission Deadline: 20:00 EST, April 12, 2004
Scope
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.
Topics
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
Publication
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
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.
Important Dates
Submission Deadline: 17:00pm (PDT), April 12th, 2004
Notification: May 26th, 2004
Camera ready: June 15th, 2004
Program Committees
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
Workshop Chairs
Klaus Jansen, U. of Kiel (E-mail: kj@informatik.uni-kiel.de)
José Rolim, U. of Geneva (E-mail: rolim@cui.unige.ch)
Steering Committee
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
Conference Web Page
http://cui.unige.ch/tcs/random-approx/.
|
