Logic List Mailing Archive
Approximation Algorithms / Ramdomization (Berkeley CA, August 2005)
CALL FOR PAPERS
APPROX 2005 + RANDOM 2005
8th. International Workshop on
Approximation Algorithms for Combinatorial Optimization Problems
and
9th. International Workshop on
Randomization and Computation
22-24 August 2005
UC Berkeley
Conference website: http://cui.unige.ch/tcs/random-approx/
SCOPE
The 8th. International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX'2005), and the
9th. International Workshop on Randomized Techniques
in Computation (RANDOM'2005) will be held at UC Berkeley,
from August 22-24, 2005.
APPROX'2005 focuses on algorithmic and complexity theoretic issues
relevant to the development of efficient approximate solutions to
computationally difficult problems, while RANDOM'2005 focuses on
applications of randomness to computational and combinatorial problems.
RANDOM'2005 is the ninth workshop in the series; APPROX'2005 is the
eighth in the series.
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
* hardness of approximation
* small space and data streaming algorithms
* sub-linear time algorithms
* embeddings and metric space methods
* mathematical progamming methods
* coloring and partitioning
* cuts and connectivity
* game theory and applications
* geometric problems
* network design and routing
* packing and covering
* scheduling
* 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, 2764, and 3122, while previous
proceedings of RANDOM appeared as LNCS 1269, 1518, 1671, 2129, 2483,
2764, 3122, and as Proceedings in Informatics 8.
GUIDELINES FOR SUBMISSION
Electronic submissions are solicited.
To submit electronically a paper or for more specific
instructions about APPROX, please consult:
http://sigact.acm.org/~approx05/approx05.html
To submit electronically a paper or for more specific
instructions about RANDOM, please consult:
http://sigact.acm.org/~random05/random05.html
The postscript must be received by 17:00pm (PDT) of April 14th for your
submission to be considered. In extreme cases, contributions may be
submitted by sending 6 hard copies to:
for APPROX:
Chandra Chekuri
Lucent Bell Labs
600 Mountain Ave, Rm 2B-425
Murray Hill, NJ 07974
for RANDOM:
Luca Trevisan
Univ of California at Berkeley
Computer Science Division
615 SODA Hall
Berkeley, CA 94720-1776
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: 5pm (PDT), April 14th, 2005
Notification: May 26th, 2005
Camera ready: June 15th, 2005
PROGRAM COMMITTEES
APPROX:
Matthew Andrews, Lucent Bell Labs
Avrim Blum, CMU
Moses Charikar, Princeton Univ.
Chandra Chekuri, Lucent Bell Labs, Chair
Julia Chuzhoy, MIT
Uri Feige, Microsoft Research & Weizmann
Naveen Garg, IIT Delhi
Howard Karloff, AT&T Labs - Research
Stavros Kolliopoulos, Univ. of Athens
Seffi Naor, Technion
Adam Meyerson, UCLA
Santosh Vempala, MIT
RANDOM:
Dorit Aharonov, Hebrew U.
Boaz Barak, IAS and Princeton U.
Funda Ergun, Simon Fraser U.
Johan Hastad, KTH Stockholm
Chi-Jen Lu, Academia Sinica
Milena Mihail, Georgia Tech.
Robi Krauthgamer, IBM Almaden
Dana Randall, Georgia Tech.
Amin Shokrollahi, EPFL Lausanne
Angelika Steger, ETH Zurich
Luca Trevisan, UC Berkeley, Chair
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
Jose Rolim, U. of Geneva
Paul Spirakis, U. of Patras
CONFERENCE WEB PAGE
http://cui.unige.ch/tcs/random-approx/