APPROX 2007 + RANDOM 2007
 Sections
  Homepage
  Call for papers and submissions
  Program
  Registration
  Accommodation
  (Social) Events
  Tourism
  Recommendations
  Conference Photos
 APPROX 2007 + RANDOM 2007

10th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems - APPROX 2007
11th Intl. Workshop on Randomization and Computation - RANDOM 2007

 
 20-22 August 2007

Princeton University
 

Scope

The 10th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2007), and the 11th. International Workshop on Randomized Techniques in Computation (RANDOM'2007) will be held at  Princeton University, on August 20-22, 2007.


APPROX'2007 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM'2007 focuses on applications of randomness to computational and combinatorial problems. RANDOM'2007 is the eleventh workshop in the series; APPROX'2007 is the tenth 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

Submissions

Abstract Format: Electronic submissions are solicited. Please consult the following servers:
For submission of APPROX papers: http://www.easychair.org/APPROX2007/
For submission of RANDOM papers: http://www.easychair.org/RANDOM2007/

Note: You will be asked to login using an EasyChair account. Directions on how to register for such an account are available at the submission servers (you may also have an old account from a previous conference submission).
 

The postscript must be received by 17:00pm (PDT) of April 7 for your submission to be considered.

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.

Simultaneous submission

Simultaneous submission to other conferences with published proceedings is not allowed.

Proceedings

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

Selected papers will be invited to a special issue of Algorithmica devoted to Approx 2007 and Random 2007.

 

Important dates

  • Submission deadline: April 7, 2007
  • Notification to authors: May 27, 2007
  • Camera ready: June 10, 2007

Program committees

APPROX 

Nikhil Bansal, IBM T J Watson
Moses Charikar, Princeton University, chair
Chandra Chekuri, University of Illinois, Urbana-Champaign
Julia Chuzhoy, IAS
Venkatesan Guruswami, University of Washington
Howard Karloff, AT&T Labs Research
Guy Kortsarz, Rutgers, Camden
Robert Krauthgamer, IBM Almaden
Claire Mathieu, Brown University
Seffi Naor, Microsoft Research and Technion
Chaitanya Swamy, University of Waterloo
Lisa Zhang, Bell Labs

RANDOM

Irit Dinur, Hebrew University
Thomas Hayes, Toyota Technological Institute at Chicago
Piotr Indyk, MIT
Russell Martin, University of Liverpool
Dieter van Melkebeek, University of Wisconsin, Madison
Michael Mitzenmacher, Harvard University
Michael Molloy, University of Toronto
Cristopher Moore, University of New Mexico
Sofya Raskhodnikova, Penn State University
Omer Reingold, Weizmann Institute, chair
Ronen Shaltiel, University of Haifa
Asaf Shapira, Microsoft Research
Aravind Srinivasan, University of Maryland
Angelika Steger, ETH Zürich
Emanuele Viola, IAS
 

Program Chairs

APPROX

Moses Charikar, Princeton University
email: moses@cs.princeton.edu

RANDOM

Omer Reingold, Weizmann Institute
email: omer.reingold@weizmann.ac.il
 

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/