Front matter
77-89
Solving Traveling Salesman Problems
Invited Lecture
William Cook
395-399
Computing Shapes from Point Cloud Data
Invited Lecture
Tamal K. Dey
37-45
Mechanism Design for Fun and Profit
Invited Lecture
Anna R. Karlin
1-16
On Distance Oracles and Routing in Graphs
Invited Lecture
Mikkel Thorup
215-216
Kinetic Medians and
kd
-Trees
Pankaj K. Agarwal, Jie Gao and Leonidas J. Guibas
243-264
Range Searching in Categorical Data: Colored Range Searching on Grid
Pankaj K. Agarwal, Sathish Govindarajan and S. Muthukrishnan
195-202
Near-Linear Time Approximation Algorithms for Curve Simplification
Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa and Yusu Wang
41-47
Translating a Planar Object to Maximize Point Containment
Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir and Michiel Smid, et al.
425-432
Approximation Algorithms for k-Line Center
Pankaj K. Agarwal, Cecilia M. Procopiuc and Kasturi R. Varadarajan
7-19
New Heuristics and Lower Bounds for the Min-Max k-Chinese Postman Problem
Dino Ahr and Gerhard Reinelt
177-178
SCIL — Symbolic Constraints in Integer Linear Programming
Ernst Althaus, Alexander Bockmayr, Matthias Elf, Michael Jünger and Thomas Kasper, et al.
161-172
Implementing I/O-efficient Data Structures Using TPIE
Lars Arge, Octavian Procopiuc and Jeffrey Scott Vitter
229-236
On the
k
-Splittable Flow Problem
Georg Baier, Ekkehard Köhler and Martin Skutella
55-99
Partial Alphabetic Trees
Arye Barkan and Haim Kaplan
313-319
Classical and Contemporary Shortest Path Problems in Road Networks: Implementation and Experimental Analysis of the TRANSIMS Router
Chris Barrett, Keith Bisset, Riko Jacob, Goran Konjevod and Madhav Marathe
335-343
Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy
Michael A. Bender, Richard Cole, Erik D. Demaine and 4Martin Farach-Colton
219-223
Two Simplified Algorithms for Maintaining Order in a List
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton and Jack Zito
165-173
Efficient Tree Layout in a Multilevel Memory Hierarchy
Michael A. Bender, Erik D. Demaine and Martin Farach-Colton
321-327
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert and Kurt Mehlhorn, et al.
21-35
TSP with Neighborhoods of Varying Size
Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos and Mark H. Overmars, et al.
401-408
1.375-Approximation Algorithm for Sorting by Reversals
Piotr Berman, Sridhar Hannenhalli and Marek Karpinski
211-222
Radio Labeling with Pre-assigned Frequencies
Hans L. Bodlaender, Hajo Broersma, Fedor V. Fomin, Artem V. Pyatkin and Gerhard J. Woeginger
223-233
Branch-and-Bound Algorithms for the Test Cover Problem
Koen M. J. De Bontridder, B. J. Lageweg, Jan K. Lenstra, James B. Orlin and Leen Stougie
145-148
Constructing Plane Spanners of Bounded Degree and Low Weight
Prosenjit Bose, Joachim Gudmundsson and Michiel Smid
183-197
Eager
st
-Ordering
Ulrik Brandes
409-416
Three-Dimensional Layers of Maxima
Adam L. Buchsbaum and Michael T. Goodrich
171-200
Optimal Terrain Construction Problems and Applications in Intensity-Modulated Radiation Therapy
Danny Z. Chen, Xiaobo S. Hu, Shuang Luan, Xiaodong Wu and Cedric X. Yu
284-296
Geometric Algorithms for Density-Based Data Clustering
Danny Z. Chen, Michiel Smid and Bin Xu
213-219
Balanced-Replication Algorithms for Distribution Trees
Edith Cohen and Haim Kaplan
201-222
Butterflies and Peer-to-Peer Networks
Mayur Datar
323-335
Estimating Rarity and Similarity over Data Stream Windows
Mayur Datar and S. Muthukrishnan
217-218
Efficient Constructions of Generalized Superimposed Codes with Applications to Group Testing and Conflict Resolution in Multiple Access Channels
Annalisa De Bonis and Ugo Vaccaro
11-20
Frequency Estimation of Internet Packet Streams with Limited Space
Erik D. Demaine, Alejandro López-Ortiz and J. Ian Munro
127-130
Truthful and Competitive Double Auctions
Kaustubh Deshmukh, Andrew V. Goldberg, Jason D. Hartline and Anna R. Karlin
203-206
Optimal Graph Exploration without Good Maps
Anders Dessmark and Andrzej Pelc
165-180
Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee
Tamal K. Dey and Wulue Zhao
399-409
Non-independent Randomized Rounding and an Application to Digital Halftoning
Benjamin Doerr and Henning Schnieder
277-288
Computing Homotopic Shortest Paths Efficiently
Alon Efrat, Stephen G. Kobourov and Anna Lubiw
207-213
An Algorithm for Dualization in Products of Lattices and Its Applications
Khaled M. Elbassioni
349-360
Determining Similarity of Conformational Polymorphs
Angela Enosh, Klara Kedem and Joel Bernstein
119-130
Minimizing the Maximum Starting Time On-line
Leah Epstein and Rob van Stee
221-228
Vector Assignment Problems: A General Framework
Leah Epstein and Tamir Tassa
107-116
Speeding Up the Incremental Construction of the Union of Geometric Objects in Practice
Eti Ezra, Dan Halperin and Micha Sharir
47-86
Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique
Torsten Fahle
89-100
Online Companion Caching
Amos Fiat, Manor Mendel and Steven S. Seiden
131-134
Deterministic Communication in Radio Networks with Large Labels
Leszek Gaşieniec, Aris Pagourtzis and Igor Potapov
27-32
A Primal Approach to the Stable Set Problem
Claudio Gentile, Haus Utz-Uwe, Matthias Köppe, Giovanni Rinaldi and Robert Weismantel
157-159
Wide-Sense Nonblocking WDM Cross-Connects
Penny Haxell, April Rasala, Gordon Wilfong and Peter Winkler
175-176
Efficient Implementation of a Minimal Triangulation Algorithm
Pinar Heggernes and Yngve Villanger
301-311
Scheduling Malleable Parallel Tasks: An Asymptotic Fully Polynomial-Time Approximation Scheme
Klaus Jansen
227-229
The Probabilistic Analysis of a Greedy Satisfiability Algorithm
Alexis C. Kaporis, Lefteris M. Kirousis and Efthimios G. Lalas
586-598
Dynamic Additively Weighted Voronoi Diagrams in 2D
Menelaos I. Karavelas and Mariette Yvinec
49-56
Time-Expanded Graphs for Flow-Dependent Transit Times
Ekkehard Köhler, Katharina Langkau and Martin Skutella
443-448
Partially-Ordered Knapsack and Applications to Scheduling
Stavros G. Kolliopoulos and George Steiner
101-130
A Software Library for Elliptic Curve Cryptography
Elisavet Konstantinou, Yiannis Stamatiou and Christos Zaroliagis
417-424
Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows
Sven O. Krumke, Jörg Rambau and Luis M. Torres
149-155
Randomized Approximation Algorithms for Query Optimization Problems on Two Processors
Eduardo Laber, Ojas Parekh and R. Ravi
662-674
Covering Things with Things
Stefan Langerman and Pat Morin
109-118
On-Line Dial-a-Ride Problems under a Restricted Information Model
Maarten Lipmann, X. Lu, Willem E. de Paepe, Rene A. Sitters and Leen Stougie
686-698
Approximation Algorithm for the Maximum Leaf Spanning Tree Problem for Cubic Graphs
Krzysztof Loryś and Grażyna Zwoźniak
135-142
Engineering a Lightweight Suffix Array Construction Algorithm
Extended Abstract
Giovanni Manzini and Paolo Ferragina
289-299
Complexity of Compatible Decompositions of Eulerian Graphs and Their Transformations
Jana Maxová and Jaroslav Nešetřil
21-26
External-Memory Breadth-First Search with Sublinear I/O
Kurt Mehlhorn and Ulrich Meyer
736-747
Frequency Channel Assignment on Planar Networks
Michael Molloy and Mohammad R. Salavatipour
157-164
Design and Implementation of Efficient Data Types for Static Graphs
Stefan Näher and Oliver Zlotowski
237-266
An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem
Benny K. Nielsen, Pawel Winter and Martin Zachariasen
17-53
A Fast, Accurate and Simple Method for Pricing European-Asian and Saving-Asian Options
Kenichiro Ohta, Kunihiko Sadakane, Akiyoshi Shioura and Takeshi Tokuyama
199-202
Sorting 13 Elements Requires 34 Comparisons
Marcin Peczarski
795-807
Extending Reduction Techniques for the Steiner Tree Problem
Tobias Polzin and Siavash Vahdati Daneshmand
181-186
A Comparison of Multicast Pull Models
Kirk Pruhs and Patchrawat Uthaisombut
173-174
Online Scheduling for Sorting Buffers
Harald Räcke, Christian Sohler and Matthias Westermann
131-144
Finding the Sink Takes Some Time
An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes
Ingo Schurr and Tibor Szabó
223-236
Lagrangian Cardinality Cuts and Variable Fixing for Capacitated Network Design
Meinolf Sellmann, Georg Kliewe and Achim Kobe stein
203-212
Minimizing Makespan and Preemption Costs on a System of Uniform Machines
Hadas Shachnai, Tami Tami and Gerhard J. Woeginger
101-106
Minimizing the Total Completion Time On-line on a Single Machine, Using Restarts
Rob van Stee and Han La Outré
147-154
High-Level Filtering for Arrangements of Conic Arcs
Extended Abstract
Ron Wein
143-146
An Approximation Scheme for Cake Division with a Linear Number of Cuts
Gerhard J. Woeginger
187-193
A Simple Linear Time Algorithm for Finding Even Triangulations of 2-Connected Bipartite Plane Graphs
Huaming Zhang and Xin He
Back matter