10. ESA 2002: Rome, Italy

Invited Lectures

• William Cook:
  Solving Traveling Salesman Problems. 1
  
• Tamal K. Dey:
  Computing Shapes from Point Cloud Data. 2
  
• Anna R. Karlin:
  Mechanism Design for Fun and Profit. 3
  
• Mikkel Thorup:
  On Distance Oracles and Routing in Graphs. 4
  

Contributed Papers

• Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas:
  Kinetic Medians and kd-Trees. 5-16
  
• Pankaj K. Agarwal, Sathish Govindarajan, S. Muthukrishnan:
  Range Searching in Categorical Data: Colored Range Searching on Grid. 17-28
  
• Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, Yusu Wang:
  Near-Linear Time Approximation Algorithms for Curve Simplification. 29-41
  
• Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel H. M. Smid, Emo Welzl:
  Translating a Planar Object to Maximize Point Containment. 42-53
  
• Pankaj K. Agarwal, Cecilia Magdalena Procopiuc, Kasturi R. Varadarajan:
  Approximation Algorithms for k-Line Center. 54-63
  
• Dino Ahr, Gerhard Reinelt:
  New Heuristics and Lower Bounds for the Min-Max k -Chinese Postman Problem. 64-74
  
• Ernst Althaus, Alexander Bockmayr, Matthias Elf, Michael Jünger, Thomas Kasper, Kurt Mehlhorn:
  SCIL - Symbolic Constraints in Integer Linear Programming. 75-87
  
• Lars Arge, Octavian Procopiuc, Jeffrey Scott Vitter:
  Implementing I/O-efficient Data Structures Using TPIE. 88-100
  
• Georg Baier, Ekkehard Köhler, Martin Skutella:
  On the k-Splittable Flow Problem. 101-113
  
• Arye Barkan, Haim Kaplan:
  Partial Alphabetic Trees. 114-125
  
• Christopher L. Barrett, Keith R. Bisset, Riko Jacob, Goran Konjevod, Madhav V. Marathe:
  Classical and Contemporary Shortest Path Problems in Road Networks: Implementation and Experimental Analysis of the TRANSIMS Router. 126-138
  
• Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton:
  Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy. 139-151
  
• Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito:
  Two Simplified Algorithms for Maintaining Order in a List. 152-164
  
• Michael A. Bender, Erik D. Demaine, Martin Farach-Colton:
  Efficient Tree Layout in a Multilevel Memory Hierarchy. 165-173
  
• Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Kurt Mehlhorn, Elmar Schömer:
  A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons. 174-186
  
• Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos, Mark H. Overmars, A. Frank van der Stappen:
  TSP with Neighborhoods of Varying Size. 187-199
  
• Piotr Berman, Sridhar Hannenhalli, Marek Karpinski:
  1.375-Approximation Algorithm for Sorting by Reversals. 200-210
  
• Hans L. Bodlaender, Hajo Broersma, Fedor V. Fomin, Artem V. Pyatkin, Gerhard J. Woeginger:
  Radio Labeling with Pre-assigned Frequencies. 211-222
  
• Koen M. J. De Bontridder, B. J. Lageweg, Jan Karel Lenstra, James B. Orlin, Leen Stougie:
  Branch-and-Bound Algorithms for the Test Cover Problem. 223-233
  
• Prosenjit Bose, Joachim Gudmundsson, Michiel H. M. Smid:
  Constructing Plane Spanners of Bounded Degree and Low Weight. 234-246
  
• Ulrik Brandes:
  Eager st-Ordering. 247-256
  
• Adam L. Buchsbaum, Michael T. Goodrich:
  Three-Dimensional Layers of Maxima. 257-269
  
• Danny Z. Chen, Xiaobo Hu, Shuang Luan, Xiaodong Wu, Cedric X. Yu:
  Optimal Terrain Construction Problems and Applications in Intensity-Modulated Radiation Therapy. 270-283
  
• Danny Z. Chen, Michiel H. M. Smid, Bin Xu:
  Geometric Algorithms for Density-Based Data Clustering. 284-296
  
• Edith Cohen, Haim Kaplan:
  Balanced-Replication Algorithms for Distribution Trees. 297-309
  
• Mayur Datar:
  Butterflies and Peer-to-Peer Networks. 310-322
  
• Mayur Datar, S. Muthukrishnan:
  Estimating Rarity and Similarity over Data Stream Windows. 323-334
  
• Annalisa De Bonis, Ugo Vaccaro:
  Efficient Constructions of Generalized Superimposed Codes with Applications to Group Testing and Conflict Resolution in Multiple Access Channels. 335-347
  
• Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
  Frequency Estimation of Internet Packet Streams with Limited Space. 348-360
  
• Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin:
  Truthful and Competitive Double Auctions. 361-373
  
• Anders Dessmark, Andrzej Pelc:
  Optimal Graph Exploration without Good Maps. 374-386
  
• Tamal K. Dey, Wulue Zhao:
  Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee. 387-398
  
• Benjamin Doerr, Henning Schnieder:
  Non-independent Randomized Rounding and an Application to Digital Halftoning. 399-410
  
• Alon Efrat, Stephen G. Kobourov, Anna Lubiw:
  Computing Homotopic Shortest Paths Efficiently. 411-423
  
• Khaled M. Elbassioni:
  An Algorithm for Dualization in Products of Lattices and Its Applications. 424-435
  
• Angela Enosh, Klara Kedem, Joel Bernstein:
  Determining Similarity of Conformational Polymorphs. 436-448
  
• Leah Epstein, Rob van Stee:
  Minimizing the Maximum Starting Time On-line. 449-460
  
• Leah Epstein, Tamir Tassa:
  Vector Assignment Problems: A General Framework. 461-472
  
• Eti Ezra, Dan Halperin, Micha Sharir:
  Speeding Up the Incremental Construction of the Union of Geometric Objects in Practice. 473-484
  
• Torsten Fahle:
  Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique. 485-498
  
• Amos Fiat, Manor Mendel, Steven S. Seiden:
  Online Companion Caching. 499-511
  
• Leszek Gasieniec, Aris Pagourtzis, Igor Potapov:
  Deterministic Communication in Radio Networks with Large Labels. 512-524
  
• Claudio Gentile, Utz-Uwe Haus, Matthias Köppe, Giovanni Rinaldi, Robert Weismantel:
  A Primal Approach to the Stable Set Problem. 525-537
  
• Penny E. Haxell, April Rasala, Gordon T. Wilfong, Peter Winkler:
  Wide-Sense Nonblocking WDM Cross-Connects. 538-549
  
• Pinar Heggernes, Yngve Villanger:
  Efficient Implementation of a Minimal Triangulation Algorithm. 550-561
  
• Klaus Jansen:
  Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial-Time Approximation Scheme. 562-573
  
• Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas:
  The Probabilistic Analysis of a Greedy Satisfiability Algorithm. 574-585
  
• Menelaos I. Karavelas, Mariette Yvinec:
  Dynamic Additively Weighted Voronoi Diagrams in 2D. 586-598
  
• Ekkehard Köhler, Katharina Langkau, Martin Skutella:
  Time-Expanded Graphs for Flow-Dependent Transit Times. 599-611
  
• Stavros G. Kolliopoulos, George Steiner:
  Partially-Ordered Knapsack and Applications to Scheduling. 612-624
  
• Elisavet Konstantinou, Yannis C. Stamatiou, Christos D. Zaroliagis:
  A Software Library for Elliptic Curve Cryptography. 625-636
  
• Sven Oliver Krumke, Jörg Rambau, Luis Torres:
  Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows. 637-648
  
• Eduardo Sany Laber, Ojas Parekh, R. Ravi:
  Randomized Approximation Algorithms for Query Optimization Problems on Two Processors. 649-661
  
• Stefan Langerman, Pat Morin:
  Covering Things with Things. 662-673
  
• Maarten Lipmann, Xiwen Lu, Willem de Paepe, René Sitters, Leen Stougie:
  On-Line Dial-a-Ride Problems under a Restricted Information Model. 674-685
  
• Krzysztof Lorys, Grazyna Zwozniak:
  Approximation Algorithm for the Maximum Leaf Spanning Tree Problem for Cubic Graphs. 686-697
  
• Giovanni Manzini, Paolo Ferragina:
  Engineering a Lightweight Suffix Array Construction Algorithm. 698-710
  
• Jana Maxová, Jaroslav Nesetril:
  Complexity of Compatible Decompositions of Eulerian Graphs and Their Transformations. 711-722
  
• Kurt Mehlhorn, Ulrich Meyer:
  External-Memory Breadth-First Search with Sublinear I/O. 723-735
  
• Michael Molloy, Mohammad R. Salavatipour:
  Frequency Channel Assignment on Planar Networks. 736-747
  
• Stefan Näher, Oliver Zlotowski:
  Design and Implementation of Efficient Data Types for Static Graphs. 748-759
  
• Benny K. Nielsen, Pawel Winter, Martin Zachariasen:
  An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem. 760-771
  
• Kenichiro Ohta, Kunihiko Sadakane, Akiyoshi Shioura, Takeshi Tokuyama:
  A Fast, Accurate and Simple Method for Pricing European-Asian and Saving-Asian Options. 772-784
  
• Marcin Peczarski:
  Sorting 13 Elements Requires 34 Comparisons. 785-794
  
• Tobias Polzin, Siavash Vahdati Daneshmand:
  Extending Reduction Techniques for the Steiner Tree Problem. 795-807
  
• Kirk Pruhs, Patchrawat Uthaisombut:
  A Comparison of Multicast Pull Models. 808-819
  
• Harald Räcke, Christian Sohler, Matthias Westermann:
  Online Scheduling for Sorting Buffers. 820-832
  
• Ingo Schurr, Tibor Szabó:
  Finding the Sink Takes Some Time. 833-844
  
• Meinolf Sellmann, Georg Kliewer, Achim Koberstein:
  Lagrangian Cardinality Cuts and Variable Fixing for Capacitated Network Design. 845-858
  
• Hadas Shachnai, Tami Tamir, Gerhard J. Woeginger:
  Minimizing Makespan and Preemption Costs on a System of Uniform Machines. 859-871
  
• Rob van Stee, Johannes A. La Poutré:
  Minimizing the Total Completion Time On-line on a Single Machine, Using Restarts. 872-883
  
• Ron Wein:
  High-Level Filtering for Arrangements of Conic Arcs. 884-895
  
• Gerhard J. Woeginger:
  An Approximation Scheme for Cake Division with a Linear Number of Cuts. 896-901
  
• Huaming Zhang, Xin He:
  A Simple Linear Time Algorithm for Finding Even Triangulations of 2-Connected Bipartite Plane Graphs. 902-914