Logic List Mailing Archive

APPROX 2006 + RANDOM 2006, Barcelona, August 2006

*************************
                           CALL FOR PAPERS
                       APPROX 2006 + RANDOM 2006
                       *************************

                     9th International Workshop on
      Approximation Algorithms for Combinatorial Optimization Problems

                                 and

      10th International Workshop on Randomization and Computation

                          28-31 August 2006
                            UPC Barcelona

               http://cui.unige.ch/tcs/random-approx/

Scope

The 9th International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX 2006), and the 10th
International Workshop on Randomized Techniques in Computation
(RANDOM 2006) will be held at UPC Barcelona, from August 28-31,
2006. APPROX 2006 focuses on algorithmic and complexity theoretic
issues relevant to the development of efficient approximate
solutions to computationally difficult problems, while RANDOM 2006
focuses on applications of randomness to computational and
combinatorial problems. RANDOM 2006 is the tenth workshop in the
series; APPROX 2006 is the ninth 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 programming 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
  * Physics methods in Computer Science

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, 3122 and 3624 while
previous proceedings of RANDOM appeared as LNCS 1269, 1518, 1671,
2129, 2483, 2764, 3122, 3624 and as Proceedings in Informatics 8.

Guidelines for Submission

Electronic submissions are solicited. To electronically submit a
paper or for more specific submission instructions, please consult
the conference web page:

http://cui.unige.ch/tcs/random-approx/

The postscript must be received by 17:00pm (PDT) of April 18th for
your submission to be considered. Simultaneous submission to other
conferences with published proceedings is not 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:   April 18th, 2006
    Notification:         May 31th, 2006
    Camera ready:        June 15th, 2006

Program Committees

APPROX

  Jittat Fakcharoenphol, Kasetsart University, Bangkok
  Uriel Feige, Microsoft Research & Weizmann Institute
  Anupam Gupta, Carnegie Mellon University, Pittsburgh
  Magnu's M. Halldo'rsson, University of Iceland
  Johan Haastad, KTH, Stockholm
  Amit Kumar, IIT, New Delhi
  James R. Lee, IAS, Princeton
  Mohammad Mahdian, Microsoft Research
  Jiri' Sgall, Academy of Sciences of the Czech Republic
  Vijay Vazirani, Georgia Institute of Technology
  Gerhard Woeginger, Eindhoven University of Technology
  Uri Zwick, Tel Aviv University, Chair

RANDOM

  Dimitris Achlioptas, UC Santa Cruz
  Andris Ambainis, U. Waterloo
  Eli Ben Sansson, Technion
  Amin Coja-Oghlan, Humbold U.
  Colin Cooper, Kings College, London
  Josep Diaz, UP Catalunya, Chair
  Ravi Kannan, Yale U.
  Colin McDiarmid, Oxford U.
  Remi Monasson, CNRS, Paris
  Alessandro Panconesi, U. Rome
  Vijaya Ramachandra, U. Texas
  Vishal Sanwalani, U. Waterloo
  Pavlos Spirakis, U. Patras
  Madhu Sudan, MIT

Program Committees Chairs

APPROX

  Uri Zwick, Tel Aviv University
  email: zwick@cs.tau.ac.il

RANDOM

  Josep Diaz, UP Catalunya
  email: diaz@lsi.upc.edu

Workshop Chairs

APPROX

  Klaus Jansen, U. of Kiel
  e-mail: kj@informatik.uni-kiel.de

RANDOM

  Jose' 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
  Jose' 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/

Organizing Committee:

C. Alvarez, M.J. Blesa, A. Duch,
H. Nesetrilova, X. Perez,  J. Petit.