CALL FOR PAPERS

I/O-Efficient Structures for Orthogonal Range Max and Stabbing Max

Pankaj K. Agarwal and Lars Arge and Jun Yang and Ke Yi

Line System Design and a Generalized Coloring Problem

Mansoor Alicherry and Randeep Bhatia

Lagrangian relaxation for the k-median problem: new insights and continuity properties

Aaron Archer and Ranjithkumar Rajagopalan and David B. Shmoys

Scheduling for Flow-Time with Admission Control

Nikhil Bansal and Avrim Blum and Shuchi Chawla and Kedar Dhamdhere

On Approximating A Geometric Traveling Salesman Problem With Time Windows

Reuven Bar-Yehuda and Guy Even and Shimon (Moni) Shahar

Semi-clairvoyant Scheduling

Luca Becchetti and Stefano Leonardi and Alberto Marchetti-Spaccamela and Kirk Pruhs

Algorithms for graph rigidity and scene analysis

Alex R. Berg and Tibor Jordan

Optimal Dynamic Video-On-Demand using Adaptive Broadcasting

Therese Biedl and Erik D. Demaine and Alexander Golynski and Joseph D. Horton and Alejandro Lopez-Ortiz and Guillaume Poirier and Claude-Guy Quimper

Multi-Player and Multi-Round Auctions with Severely Bounded Communication

Liad Blumrosen and Noam Nisan and Ilya Segal

Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks

Gruia Calinescu, Sanjiv Kapoor, Alex Olshevsky, Alex Zelikovsky

Disjoint Unit Spheres Admit At Most Two Line Transversals

Otfried Cheong and Xavier Goaoc and Hyeon-Suk Na

An Optimal Algorithm for the Maximum-Density Segment Problem

Kai-min Chung and Hsueh-I Lu

Estimating Dominance Norms of Multiple Data Streams

Graham Cormode and S. Muthukrishnan

Smoothed Motion Complexity

Valentina Damerow and Friedhelm Meyer auf der Heider and Harald Raecke and Christian Scheideler and Christian Sohler

Kinetic Dictionaries: How to Shoot a Moving Target

Mark de Berg

Deterministic rendezvous in graphs

A. Dessmark and P. Fraigniaud and A. Pelc

Binary Space Partition for Orthogonal Fat Rectangles

Csaba D. Toth

Correlation Clustering -- Minimizing Disagreements on Arbitrary Weighted Graphs

Dotan Emanuel and Amos Fiat

Fast integer programming in fixed dimension

Friedrich Eisenbrand

Dominating sets and local treewidth

Fedor V. Fomin and Dimitrios M. Thilikos

Approximating Energy Efficient Paths in Wireless Multi-Hop Networks

Stefan Funke and Domagoj Matijevic and Peter Sanders

Bandwidth Maximization in Multicasting

Naveen Garg and Rohit Khandekar and Keshav Kunal and Vinayaka Pandit

Optimal Distance Labeling Schemes

Cyril Gavoille and Christophe Paul

Improved Approximation of the Stable Marriage Problem

Magnus Halldorsson and Kazuo Iwama and Shuichi Miyazaki and Hiroki Yanagisawa

Fast Algorithms for Computing the Smallest k-Enclosing Disc

Sariel Har-Peled and Soham Mazumdar

The minimum generalized vertex cover problem

Refael Hassin and Asaf Levin

An Approximation Algorithm for MAX-2-SAT with Cardinality Constraint

Thomas Hofmeister

On Demand Broadcasting Under Deadline

Bala Kalyanasundaram and Mahe Velauthapillai

Improved Bounds for Finger Search on a RAM

Alexis Kaporis and Christos Makris and Spyros Sioutas and Athanasios Tsakalidis and Kostas Tsichlas and Christos Zaroliagis

The Voronoi Diagram of Convex Objects in the Plane

Menelaos I. Karavelas and Mariette Yvinec

Improved Competitive Guarantees for QoS Buffering

Alex Kesselman and Yishay Mansour and Rob van Stee

Buffer Overflows of Merging Streams

Kesselman and Lotker and Mansour and Patt-Shamir

On generalized gossiping and broadcasting

Samir Khuller and Yoo-Ah Kim and Yung-Chun Wan

Approximating the achromatic number problem on bipartite graphs

Guy Kortsarz and Sunil Shende

Adversary Immune Leader Election in Ad Hoc Radio Networks.

Miroslaw Kutylowski and Wojciech Rutkowski

Universal Facility Location

Mohammad Mahdian and Martin Pal

A Method for Creating Near-Optimal Instances of a Certified Write-All Algorithm

Grzegorz Malewicz

I/O-Efficient Undirected Shortest Paths

Ulrich Meyer and Norbert Zeh

On the Complexity of Approximating TSP with Neighborhoods and related problems

Oded Schwartz and Shmuel Safra

A lower bound for cake cutting

Jiri Sgall and Gerhard Woeginger

Ray Shooting and Stone Throwing

Micha Sharir and Hayim Shaul

Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs

Aleksandrs Slivkins

Sequencing by Hybridization in Few Rounds

Dekel Tsur

Efficient Algorithms for the Ring Loading Problem with Demand Splitting

Biing-Feng Wang, Yong-Hsian Hsieh, and Li-Pu Yeh

Seventeen lines and one-hundred-and-one points

Jacobi Curves: Computing the Exact Topologie of Arrangements of Non-Singular Algebraic Curves

Streaming Geometric Optimization using Graphics Hardware

Pankaj Agarwal, Shankar Krishnan, Nabil Mustafa and Suresh Venkatasubramanian

An Efficient Implementation of a Quasi-Polynomial Algorithm for Generating Hypergraph Transversals

E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan

Experiments on Graph Clustering Algorithms

Ulrik Brandes, Marco Gaertler and Dorothea Wagner

More Reliable Protein NMR Peak Assignment via Improved 2-Interval

Zhi-Zhong Chen, Tao Jiang, Guohui Lin, Romeo Rizzi and Jianjun Wen

The minimum shift design problem: theory and practice

Luca Di Gaspero, Johannes Gaertner, Guy Kortsarz Nysret Musliu, Andrea Schaerf and Wolfgang Slany

Loglog Counting of Large Cardinalities

Marianne Durand and Philippe Flajolet

Packing a Trunk

Friedrich Eisenbrand, Stefan Funke, Joachim Reichel and Elmar Shomer

Fast Smallest-Enclosing-Ball Computation in High Dimensions

Kaspar Fischer, Bernd Gaertner and Martin Kutz

Automated Generation of Search Tree Algorithms for Graph Modification Problems

Jens Gramm, Jiong Guo, Falk Hueffner and Rolf Niedermeier

Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation

Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn and Michael Seel

Fleet Assignment with Connection dependent Ground Times

Sven Grothklags

A Practical Minimum Spanning Tree Algorithm Using the Cycle Property

Irit Katriel, Peter Sanders and Jesper Larsson Traeff

The Fractional Prize-Collecting Steiner Tree Problem on Trees

Gunnar Klau, Ivana Ljubic, Petra Mutzel, Ulrich Pferschy and Rene Weiskircher

Finding Short Integer Cycle Bases for Cyclic Timetabling

Christian Liebchen

Algorithms and Experiments for the Webgraph

Luigi Laura, Stefano Leonardi, Stefano Millozzi and Ulrich Meyer

Slack Optimization of Timing-Critical Nets

Matthias Mueller-Hannemann and Ute Zimmermann

Multisampling: a New Approach to Uniform Sampling and Approximate

Piotr Sankowski

Multicommodity Flow Approximation used for Exact Graph Partitioning

Meinolf Sellmann, Norbert Sensen and Larissa Timajev

A linear time heuristic for the branch-decomposition of planar graphs

Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs

Dorothea Wagner and Thomas Willhalm

16 September
Session 1A	Session 1B
09.00-09.25 Fast integer programming in fixed dimension Friedrich Eisenbrand	09.00-09.25 Streaming Geometric Optimization using Graphics Hardware Pankaj Agarwal, Shankar Krishnan, Nabil Mustafa and Suresh Venkatasubramanian
09.25-09.50 Fast Smallest-Enclosing-Ball Computation in High Dimensions Kaspar Fischer, Bernd Gaertner and Martin Kutz	09.25-09.50 Estimating Dominance Norms of Multiple Data Streams Graham Cormode and S. Muthukrishnan
Session 2 A	Session 2 B
10.20-10.45 Optimal Dynamic Video-On-Demand using Adaptive Broadcasting Therese Biedl and Erik D. Demaine and Alexander Golynski and Joseph D. Horton and Alejandro Lopez-Ortiz and Guillaume Poirier and Claude-Guy Quimper	10.20-10.45 Ray Shooting and Stone Throwing Micha Sharir and Hayim Shaul
10.45-11.10 On Demand Broadcasting Under Deadline Bala Kalyanasundaram and Mahe Velauthapillai	10.45-11.10 Kinetic Dictionaries: How to Shoot a Moving Target Mark de Berg
Invited talk Sublinear Computing Bernard Chazelle 11.20-12.10
Session 3A	Session 3B
14.00-14.25 Universal Facility Location Mohammad Mahdian and Martin Pal	14.00-14.25 Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn and Michael Seel
14.25-14.50 Lagrangian relaxation for the k-median problem: new insights and continuity properties Aaron Archer and Ranjithkumar Rajagopalan and David B. Shmoys	14.25-14.50 Jacobi Curves: Computing the Exact Topologie of Arrangements of Non-Singular Algebraic Curves Nicola Wolpert
14.50-15.15 Multicommodity Flow Approximation used for Exact Graph Partitioning Meinolf Sellmann, Norbert Sensen and Larissa Timajev	14.50-15.15 The Voronoi Diagram of Convex Objects in the Plane Menelaos I. Karavelas and Mariette Yvinec
Session 4A	Session 4B
15.45-16.10 Seventeen lines and one-hundred-and-one points Gerhard Woeginger	15.45-16.10 Dominating sets and local treewidth Fedor V. Fomin and Dimitrios M. Thilikos
16.10-16.35 Packing a Trunk Frederick Eisenbrand, Stefan Funke, Joachim Reichel and Elmar Shomer	16.10-16.25 Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs Aleksandrs Slivkins
17 September
Session 5A	Session 5B
09.00-09.25 A lower bound for cake cutting Jiri Sgall and Gerhard Woeginger	09.00-09.25 An Efficient Implementation of a Quasi -Polynomial Algorithm for Generating Hypergraph Transversals E. Boros, K. Elbassioni, V. Gurvich, and L. Khachiyan
09.25-09.50 Multi-Player and Multi-Round Auctions with Severely Bounded Communication Liad Blumrosen and Noam Nisan and Ilya Segal	09.25-09.50 Finding Short Integer Cycle Bases for Cyclic Timetabling Christian Liebchen
Session 6 A	Session 6B
10.20-10.45 Loglog Counting of Large Cardinalities Marianne Durand and Philippe Flajolet	10.20-10.45 Improved Competitive Guarantees for QoS Buffering Alex Kesselman and Yishay Mansour and Rob van Stee
10.45-11.10 Multisampling: a New Approach to Uniform Sampling and Approximate Counting Piotr Sankowski	10.45-11.10 Buffer Overflows of Merging Streams Kesselman and Lotker and Mansour and Patt-Shamir
Invited talk Approximation Algorithms and Network Games Eva Tardos 11.20-12.10
Session 7A	Session 7B
14.00-14.25 Semi-clairvoyant Scheduling Luca Becchetti and Stefano Leonardi and Alberto Marchetti-Spaccamela and Kirk Pruhs	14.00-14.25 On generalized gossiping and broadcasting Samir Khuller and Yoo-Ah Kim and Yung-Chun Wan
14.25-14.50 Scheduling for Flow-Time with Admission Control Nikhil Bansal and Avrim Blum and Shuchi Chawla and Kedar Dhamdhere	14.25-14.50 Bandwidth Maximization in Multicasting Naveen Garg and Rohit Khandekar and Keshav Kunal and Vinayaka Pandit
14.50-15.15 More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling Zhi-Zhong Chen, Tao Jiang, Guohui Lin, Romeo Rizzi and Jianjun Wen	14.50-15.15 Efficient Algorithms for the Ring Loading Problem with Demand Splitting Biing-Feng Wang, Yong-Hsian Hsieh, and Li-Pu Yeh
Session 8A	Session 8B
15.45-16.10 Improved Bounds for Finger Search on a RAM Alexis Kaporis and Christos Makris and Spyros Sioutas and Athanasios Tsakalidis and Kostas Tsichlas and Christos Zaroliagis	15.45-16.10 A Method for Creating Near-Optimal Instances of a Certified Write-All Algorithm Grzegorz Malewicz
16.10-16.35 Smoothed Motion Complexity Valentina Damerow and Friedhelm Meyer auf der Heider and Harald Raecke and Christian Scheideler and Christian Sohler	16.10-16.35 Line System Design and a Generalized Coloring Problem Mansoor Alicherry and Randeep Bhatia
18 September
Session 9A	Session 9B
09.00-09.25 Correlation Clustering -- Minimizing Disagreements on Arbitrary Weighted Graphs Dotan Emanuel and Amos Fiat	09.00-09.25 Sequencing by Hybridization in Few Rounds Dekel Tsur
09.25-09.50 Experiments on Graph Clustering Algorithms Ulrik Brandes, Marco Gaertler and Dorothea Wagner	09.25-09.50 An Optimal Algorithm for the Maximum-Density Segment Problem Kai-min Chung and Hsueh-I Lu
Session 10A	Session 10B
10.20-10.45 A Practical Minimum Spanning Tree Algorithm Using the Cycle Property Irit Katriel, Peter Sanders and Jesper Larsson Traeff	10.20-10.45 Optimal Distance Labeling for interval and circular-arc graphs Cyril Gavoille and Christophe Paul
10.45-11.10 Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs Dorothea Wagner and Thomas Willhalm	10.45-11.10 Deterministic rendezvous in graphs A. Dessmark and P. Fraigniaud and A. Pelc
Invited talk Molecular structure motif discovery Francois Major 11.20-12.10
Session 11A	Session 11B
14.00-14.25 Algorithms and Experiments for the Webgraph Luigi Laura, Stefano Leonardi, Stefano Millozzi and Ulrich Meyer	14.00-14.25 On the Complexity of Approximating TSP with Neighborhoods and related problems Oded Schwartz and Shmuel Safra
14.25-14.50 I/O-Efficient Undirected Shortest Paths Ulrich Meyer and Norbert Zeh	14.25-14.50 On Approximating a Geometric Prize-Collecting Traveling Salesman Problem With Time Windows Reuven Bar-Yehuda and Guy Even and Shimon (Moni) Shahar
14.50-15.15 I/O-Efficient Structures for Orthogonal Range Max and Stabbing Max Pankaj K. Agarwal and Lars Arge and Jun Yang and Ke Yi	14.50-15.15 The Fractional Prize-Collecting Steiner Tree Problem on Trees Gunnar Klau, Ivana Ljubic, Petra Mutzel, Ulrich Pferschy and Rene Weiskircher
Session 12A	Session 12B
15.45-16.10 Algorithms for graph rigidity and scene analysis Alex R. Berg and Tibor Jordan	15.45-16.10 The minimum generalized vertex cover problem Refael Hassin and Asaf Levin
16.10-16.35 A linear time heuristic for the branch-decomposition of planar graphs Hisao Tamaki	16.10-16.35 An Approximation Algorithm for MAX-2-SAT with Cardinality Constraint Thomas Hofmeister
19 September
Session 13A	Session 13B
09.00-09.25 Binary Space Partition for Orthogonal Fat ectangles Csaba D. Toth	09.00-09.25 The minimum shift design problem: theory and practice Luca Di Gaspero, Johannes Gaertner, Guy Kortsarz, Nysret Musliu, Andrea Schaerf and Wolfgang Slany
09.25-09.50 Disjoint Unit Spheres Admit At Most Two Line Transversals Otfried Cheong and Xavier Goaoc and Hyeon-Suk Na	09.25-09.50 Fleet Assignment with Connection dependent Ground Times Sven Grothklags
Session 14A	Session 14B
10.20-10.45 Fast Algorithms for Computing the Smallest k-Enclosing Disc Sariel Har-Peled and Soham Mazumdar	10.20-10.45 Automated Generation of Search Tree Algorithms for Graph Modification Problems Jens Gramm, Jiong Guo, Falk Hueffner and Rolf Niedermeier
Invited talk Authenticated data structures Roberto Tamassia 11.20-12.10
Session 15A	Session 15B
14.00-14.25 Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks Gruia Calinescu, Sanjiv Kapoor, Alex Olshevsky, Alex Zelikovsky	14.00-14.25 Approximating the achromatic number problem on bipartite graphs Guy Kortsarz and Sunil Shende
14.25-14.50 Adversary Immune Leader Election in Ad Hoc Radio Networks. Miroslaw Kutylowski and Wojciech Rutkowski	14.25-14.50 Improved Approximation of the Stable Marriage Problem Magnus Halldorsson and Kazuo Iwama and Shuichi Miyazaki and Hiroki Yanagisawa
14.50-15.15 Approximating Energy Efficient Paths in Wireless Multi-Hop Networks Stefan Funke and Domagoj Matijevic and Peter Sanders	14.50-15.15 Slack Optimization of Timing-Critical Nets Matthias Mueller-Hannemann and Ute Zimmermann

The deadline for receiving the final version is JUNE 30, 2003. This is a STRICT deadline. Papers arriving too late will not be included in the proceedings.

When preparing the final version, please observe the STRICT limit of 12 pages in standard LNCS style (particularly with respect to page margins and font size). Also, do not use page numbers or running heads as these will be added later by Springer. Please consult http://www.springer.de/comp/lncs/authors.html for the definition of the LNCS style and for sample files.

Important: Do not change any settings of the Springer style file! Springer will latex everything again according to their settings and you may risk a mutilated appearance in the proceedings otherwise.

When you have completed the final version, please prepare a compressed archive containing the files. This compressed archive should be created using either tar/gzip or it should be a zip archive compatible with WinZip 8.0. Please name this file A_xx_lastname.tar.gz or A_xx_lastname.zip, respectively, where lastname is the last name of the corresponding author, and xx is the string assigned to the paper by the submission server (e.g., alb-84032).

This zip archive should contain:

1) a PS or PDF file with the final camera-ready submission.

Please ensure that all fonts are embedded and that the file can be printed. Please name this file A_xx_lastname.{ps,pdf} which is intepreted as above.

The source file should be a LaTex file as required by LNCS. Please follow the naming convention A_xx_lastname.tex for the "top-level" file. You should include any necessary additional source files, such as special class files, images or figures as separate files.

Please email this as attachment with A_xx_lastname on the subject line to esa03a@cs.tau.ac.il before the above deadline.

As a last step, snail mail or fax a signed copy of Springer's copyright form to Uri Zwick. (If you fax the form, please attach a header page saying explicitly that the fax is for Uri Zwick.) You can find the form at

School of Computer Science

Best regards and see you in Budapest!

The deadline for receiving the final version is JUNE 30, 2003. This is a STRICT deadline. Papers arriving too late will not be included in the proceedings.

Important: Do not change any settings of the Springer style file! Springer will latex everything again according to their settings and you may risk a mutilated appearance in the proceedings otherwise.

When you have completed the final version, please prepare a compressed archive containing the files. This compressed archive should be created using either tar/gzip or it should be a zip archive compatible with WinZip 8.0. Please name this file B_xx_lastname.tar.gz or B_xx_lastname.zip, respectively, where lastname is the last name of the corresponding author, and xx is the string assigned to the paper by the submission server (e.g., alb-84032).

This zip archive should contain:

1) a PS or PDF file with the final camera-ready submission. Please ensure that all fonts are embedded and that the file can be printed. Please name this file B_xx_lastname.{ps,pdf} which is intepreted as above.

The source file should be a LaTex file as required by LNCS. Please follow the naming convention B_xx_lastname.tex for the "top-level" file. You should include any necessary additional source files, such as special class files, images or figures as separate files.

Please email this as attachment with B_xx_lastname on the subject line to gdb@dia.uniroma3.it before the above deadline.

As a last step, snail mail or fax a signed copy of Springer's copyright form to Giuseppe Di Battista. (If you fax the form, please attach a header page saying explicitly that the fax is for Giuseppe Di Battista.) You can find the form at http://www.springer.de/comp/lncs/copyright.html

Prof. Giuseppe Di Battista

Dipartimento di Informatica e Automazione

Universita' di Roma Tre

via della Vasca Navale, 79

TEL: +39-06-55173209

Best regards and see you in Budapest!

Giuseppe Di Battista