Approximation Algorithms for Combinatorial Optimization Problems
APPROX 2000
Saarbruecken, September 5-8
Invited talks:
Sanjeev Arora:
Approximation algorithms that take advice
Dorit Hochbaum:
TBA
Rolf M\"ohring:
Scheduling under uncertainty: Optimizing against a randomizing adversary
David Shmoys:
Approximation algorithms for facility locations problems
------------------------------------------------------------------------------
List of accepted papers:
Alexander Ageev, Refael Hassin and Maxim Sviridenko:
An Approximation Algorithm for MAX DICUT with Given Sizes of Parts
[log in to unmask]
Baruch Awerbuch, Yossi Azar and Oded Regev:
Maximizing Job Benefits On-line
[log in to unmask]
Piotr Berman and Junichiro Fukuyama:
Variable length sequencing with two lengts
{berman,[log in to unmask]
Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis and Pino Persiano:
Randomized Path Coloring on Binary Trees
[log in to unmask]
Alberto Caprara, Giuseppe F. Italiano, G. Mohan, Alessandro Panconesi
and Aravind Srinivasan:
Wavelenght Rerouting in Optical Networks, or the Venetian Routing Problem
[log in to unmask]
Moses Charikar:
Greedy Approximation Algorithms for Finding Dense Components in a Graph
[log in to unmask]
Bhaskar DasGupta and Michael A. Palis:
Online Real-Time Preemptive Scheduling of Jobs with Deadlines
{bhaskar,[log in to unmask]
Martin Dyer, Leslie Ann Golberg, Catherine Greenhill and Mark Jerrum:
On the relative complexity of approximate counting problems
[log in to unmask]
Uriel Feige, Michael Langberg and Kobbi Nissim:
On the hardness of approximating NP witnesses
{feige, mikel, [log in to unmask]
Sandor P. Fekete and Henk Meijer:
Maximum Dispersion and Geometric Maximum Weight Cliques
[log in to unmask]
Rudolf Fleischer and Steve Seiden:
New Results for Online Page Replication
[log in to unmask],[log in to unmask]
Venkatesan Guruswami:
Inapproximability Results for Set Splitting and Satisfiability
Problems with no Mixed Clauses
[log in to unmask]
R. Hassin, R. Ravi and F.S. Salman:
Approximation Algorithms for a Capacitated Network Design Problem
[log in to unmask]
Kamal Jain and Vijay Vazirani:
An Approximation Algorithm for Fault Tolerant Metric Facility Location Problems
{kjain,[log in to unmask]
Jochen Koenemann, Goran Konjevod, Ojas Parekh and Amitabh Sinha:
Improved approximations for tour and tree covers
[log in to unmask]
Stavros G. Kolliopoulos:
Approximating Covering Integer Programs with Multiset Constraints
[log in to unmask]
Guy Kortsarz and Zeev Nutov:
Approximating node connectivity problems via set covers
[log in to unmask],[log in to unmask]
Krzysztof Lorys and Katarzyna Paluch:
Rectangle Tiling
[log in to unmask]
Tobias Polzin and Siavash V. Daneshmand:
Primal-Dual Approaches to the Steiner Problem
{polzin,[log in to unmask]
Christian Schindelhauer:
On the Inapproximability of Broadcasting Time
[log in to unmask]
Hadas Shachnai and Tami Tamir:
Polynomial Time Approximation Schemes for Class-Constrained Packing Problems
[log in to unmask]
Rob van Stee and Han L. Poutre:
Partial Servicing of On-line Jobs
{rvs,[log in to unmask]
Santosh Vempala and Adrian Vetta:
Factor 4/3 Approximations for Minimum 2-Connected Subgraphs
{vempala,[log in to unmask]
------------------------------------------------------------------------------
Further informations under:
http://www.mpi-sb.mpg.de/~conf2000/approx2000/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
