Logic List Mailing Archive
APPROX-RANDOM (8th workshop on Approximation Algorithms + 9th Workshop on Randomization); Berkeley August 2005
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
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/