| Tuesday, August 7 | |
| Reception: 7:00pm-9:00pm (CIT 5th floor) | |
| Wednesday, August 8 | |
| Breakfast: 8:45-9:30 | |
| Session 1: 9:30 - 10:30 (McMillan 117) Invited Lecture: Approximation of Multiobjective Optimization Problems. Mihalis Yannakakis | |
| Track A | Track B |
| Coffee Break: 10:30 - 11:00 (McMillan Lobby) | |
| Session 2A: 11:00 - 12:00 | Session 2B: 11:00 - 12:00 |
| Optimal, Suboptimal and Robust Algorithms for Proximity Graphs. F. Hurtado, G. Liotta, H. Meijer | Using the pseudo-dimension to analyze approximation algorithms for integer programming. Philip M. Long |
| Optimal Moebius Transformations for Information Visualization and Meshing. Marshall Bern and David Eppstein | On the Complexity of Scheduling Conditional Real-Time Code. Samarjit Chakraborty and Thomas Erlebach and Lothar Thiele |
| Lunch: 12:00-1:30 (CIT 4th floor) | |
| Session 3A: 1:30 - 2:30 | Session 3B: 1:30 - 2:30 |
| Time Responsive External Data Structures for Moving Points. Pankaj K. Agarwal and Lars Arge and Jan Vahrenhold | Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover. Naomi Nishimura and Prabhakar Ragde and Dimitrios M. Thilikos |
| Voronoi Diagrams for Moving Disks and Applications. Menelaos I. Karavelas | Minimizing clique-width for graphs of bounded tree-width. Wolfgang Espelage, Frank Gurski, Egon Wanke |
| Coffee Break: 2:30 - 3:00 (McMillan Lobby) | |
| Session 4A: 3:00 - 4:30 | Session 4B: 3:00 - 4:30 |
| Complexity Bounds for Vertical Decompositions of Linear Arrangements in . Vladlen Koltun | Seller-Focused Algorithms for Online Auctioning. Amitabha Bagchi and Amitabh Chaudhary and Rahul Garg and Michael T. Goodrich and Vijay Kumar |
| Optimization Over Zonotopes and Training Support Vector Machines. Marshall Bern and David Eppstein | Competitive analysis of the LRFU paging algorithm. Edith Cohen and Haim Kaplan and Uri Zwick |
| Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions. Pankaj K. Agarwal and Mark de Berg and Sariel Har-Peled and Mark Overmars and Micha Sharir and Jan Vahrenhold | Admission Control to Minimize Rejections. Avrim Blum and Adam Kalai and Jon Kleinberg |
| Thursday, August 9 | |
| Breakfast: 8:45-9:30 (McMillan Lobby) | |
| Session 5: 9:30 - 10:30 Invited Lecture: Secure Multi-Party Computational Geometry. Mikhail J. Atallah (joint work with Wenliang (Kevin) Du) | |
| Track A | Track B |
| Coffee Break: 10:30 - 11:00 (McMillan Lobby) | |
| Session 6A: 11:00 - 12:00 | Session 6B: 11:00 - 12:00 |
| The Grid Placement Problem. P. Bose, A. Maheshwari, P. Morin, and J. Morrison | A (7/8)-approximation algorithm for metric Max TSP. Refael Hassin and Shlomi Rubinstein |
| On the Reflexivity of Point Sets. Esther M. Arkin and S\'andor P. Fekete and Ferran Hurtado and Joseph S. B. Mitchell Marc Noy and Vera Sacrist\'an and Saurabh Sethia | Approximating Multi-Objective Knapsack Problems. Thomas Erlebach and Hans Kellerer and Ulrich Pferschy |
| Lunch: 12:00-1:30 (Sharpe Refectory) | |
| Session 7A: 1:30 - 2:30 | Session 7B: 1:30 - 2:30 |
| Visual Ranking of Link Structures. Ulrik Brandes and Sabine Cornelsen | Short and simple labels for small distances and other functions. Haim Kaplan and Tova Milo |
| A simple linear time algorithm for proper box rectangular drawings of plane graphs. Xin He | Fast Boolean matrix multiplication for highly clustered data. Andreas Bjorklund and Andrzej Lingas |
| Coffee Break: 2:30 - 3:00 (McMillan Lobby) | |
| Session 8A: 3:00 - 4:30 | Session 8B: 3:00 - 4:30 |
| Partitioning colored point sets into monochromatic parts. Adrian Dumitrescu and Janos Pach | Higher-Dimensional Packing with Order Constraints. S\'andor P. Fekete and Ekkehard K\"ohler and J\"urgen Teich |
| The Analysis of a Probabilistic Approach to Nearest Neighbor Searching. Songrit Maneewongvatana and David M. Mount | Bin Packing with Item Fragmentation. Nir Menakerman and Raphael Rom |
| I/O-Efficient Shortest Path Queries in Geometric Spanners. Anil Maheshwari and Michiel Smid and Norbert Zeh | Practical Approximation Algorithms for Separable Linear Programs. F.F. Dragan and A.B. Kahng and I.I. Mandoiu and S. Muddu |
| Banquet: 6:30-9:30 (Faculty Club) | |
| Friday, August 10 | |
| Breakfast: 8:45-9:30 | |
| Session 9: 9:30 - 10:30 Invited Lecture: The Challenges of Delivering Content on the Internet. F. Thomson Leighton | |
| Track A | Track B |
| Coffee Break: 10:30 - 11:00 (McMillan Lobby) | |
| Session 10A: 11:00 - 12:00 | Session 10B: 11:00 - 12:00 |
| Upward Embeddings and Orientations of Undirected Planar Graphs. Walter Didimo and Maurizio Pizzonia | A Linear-Time Algorithm for Computing Inversion Distance Between Signed Permutations with an Experimental Study. David A. Bader and Bernard M.E. Moret and Mi Yan |
| An Approach for Mixed Upward Planarization . Markus Eiglsperger and Michael Kaufmann | Computing Phylogenetic Roots with Bounded Degrees and Errors . Zhi-Zhong Chen and Tao Jiang and Guo-Hui Lin |
| Lunch: 12:00-1:30 (Sharpe Refectory) | |
| Session 11A: 1:30 - 2:30 | Session 11B: 1:30 - 2:30 |
| A decomposition-based approach to layered manufacturing. Ivaylo Ilinkin and Ravi Janardan and Jayanth Majhi and Joerg Schwerdt and Michiel Smid and Ram Sriram | Search Trees with Relaxed Balance and Near-Optimal Height. Rolf Fagerberg and Rune E. Jensen and Kim S. Larsen |
| When Can You Fold a Map?. Esther M. Arkin and Michael A. Bender and Erik D. Demaine and Martin L. Demaine and Joseph S. B. Mitchell and Saurabh Sethia and Steven S. Skiena | Succint Dynamic Data Structures. Rajeev Raman and Venkatesh Raman and S. Srinivasa Rao |
| Coffee Break: 2:30 - 3:00 (McMillan Lobby) | |
| Session 12A: 3:00 - 4:00 | Session 12B: 3:00 - 4:00 |
| Two-Guard Walkability of Simple Polygons. Binay Bhattacharya, Asish Mukhopadhyay, Giri Narasimhan | Small Maximal Independent Sets and Faster Exact Graph Coloring. David Eppstein |
| Movement Planning in the Presence of Flows. John Reif and Zheng Sun | On External-Memory Planar Depth First Search. Lars Arge, Ulrich Meyer, Laura Toma, Norbert Zeh |