Front matter
1
Approximation of Multiobjective Optimization Problems
Mihalis Yannakakis
2-13
Optimal, Suboptimal, and Robust Algorithms for Proximity Graphs
Ferran Hurtado, Giuseppe Liotta and Henk Meijer
14-25
Optimal Möbius Transformations for Information Visualization and Meshing
Marshall Bern and David Eppstein
26-37
Using the Pseudo-Dimension to Analyze Approximation Algorithms for Integer Programming
Philip M. Long
38-49
On the Complexity of Scheduling Conditional Real-Time Code
Samarjit Chakraborty, Thomas Erlebach and Lothar Thiele
50-61
Time Responsive External Data Structures for Moving Points
Pankaj K. Agarwal, Lars Arge and Jan Vahrenhold
62-74
Voronoi Diagrams for Moving Disks and Applications
Menelaos I. Karavelas
75-86
Fast Fixed-Parameter Tractable Algorithms for Nontrivial Generalizations of Vertex Cover
Naomi Nishimura, Prabhakar Ragde and Dimitrios M. Thilikos
87-98
Deciding Clique-Width for Graphs of Bounded Tree-Width
Extended Abstract
Wolfgang Espelage, Frank Gurski and Egon Wanke
99-110
Complexity Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions
Vladlen Koltun
111-121
Optimization over Zonotopes and Training Support Vector Machines
Marshall Bern and David Eppstein
122-134
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions
Pankaj K. Agarwal, Mark de Berg, Sariel Har-Peled, Mark H. Overmars and Micha Sharir, et al.
135-147
Seller-Focused Algorithms for Online Auctioning
Amitabha Bagchi, Amitabh Chaudhary, Rahul Garg, Michael T. Goodrich and Vijay Kumar
148-154
Competitive Analysis of the LRFU Paging Algorithm
Edith Cohen, Haim Kaplan and Uri Zwick
155-164
Admission Control to Minimize Rejections
Avrim Blum, Adam Kalai and Jon Kleinberg
165-179
Secure Multi-party Computational Geometry
Mikhail J. Atallah and Wenliang Du
180-191
The Grid Placement Problem
Prosenjit Bose, Anil Maheshwari, Pat Morin and Jason Morrison
192-204
On the Reflexivity of Point Sets
Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Joseph S. B. Mitchell and Marc Noy, et al.
205-209
A 7/8-Approximation Algorithm for Metric Max TSP
Refael Hassin and Shlomi Rubinstein
210-221
Approximating Multi-objective Knapsack Problems
Thomas Erlebach, Hans Kellerer and Ulrich Pferschy
222-233
Visual Ranking of Link Structures
Extended Abstract
Ulrik Brandes and Sabine Cornelsen
234-245
A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs
Xin He
246-257
Short and Simple Labels for Small Distances and Other Functions
Haim Kaplan and Tova Milo
258-263
Fast Boolean Matrix Multiplication for Highly Clustered Data
Andreas Björklund and Andrzej Lingas
264-275
Partitioning Colored Point Sets into Monochromatic Parts
Adrian Dumitrescu and János Pach
276-286
The Analysis of a Probabilistic Approach to Nearest Neighbor Searching
Songrit Maneewongvatana and David M. Mount
287-299
I/O-Efficient Shortest Path Queries in Geometric Spanners
Anil Maheshwari, Michiel Smid and Norbert Zeh
300-312
Higher-Dimensional Packing with Order Constraints
Sándor P. Fekete, Ekkehard Köhler and Jürgen Teich
313-324
Bin Packing with Item Fragmentation
Nir Menakerman and Raphael Rom
325-337
Practical Approximation Algorithms for Separable Packing Linear Programs
Feodor F. Dragan, Andrew B. Kahng, Ion I. Măndoiu, Sudhakar Muddu and Alexander Zelikovsky
338
The Challenges of Delivering Content on the Internet
F. Thomson Leighton
339-351
Upward Embeddings and Orientations of Undirected Planar Graphs
Walter Didimo and Maurizio Pizzonia
352-364
An Approach for Mixed Upward Planarization
Markus Eiglsperger and Michael Kaufmann
365-376
A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study
David A. Bader, Bernard M. E. Moret and Mi Yan
377-388
Computing Phylogenetic Roots with Bounded Degrees and Errors
Extended Abstract
Zhi-Zhong Chen, Tao Jiang and Guo-Hui Lin
389-400
A Decomposition-Based Approach to Layered Manufacturing
Ivaylo Ilinkin, Ravi Janardan, Jayanth Majhi, Jörg Schwerdt and Michiel Smid, et al.
401-413
When Can You Fold a Map?
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine and Joseph S. B. Mitchell, et al.
414-425
Search Trees with Relaxed Balance and Near-Optimal Height
Rolf Fagerberg, Rune E. Jensen and Kim S. Larsen
426-437
Succinct Dynamic Data Structures
Rajeev Raman, Venkatesh Raman and S. Srinivasa Rao
438-449
Optimal Algorithms for Two-Guard Walkability of Simple Polygons
Binay Bhattacharya, Asish Mukhopadhyay and Giri Narasimhan
450-461
Movement Planning in the Presence of Flows
John Reif and Zheng Sun
462-470
Small Maximal Independent Sets and Faster Exact Graph Coloring
David Eppstein
471-482
On External-Memory Planar Depth First Search
Lars Arge, Ulrich Meyer, Laura Toma and Norbert Zeh
Back matter