WADS 2001 Program

Plain Text Version

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 ATrack B
Coffee Break: 10:30 - 11:00 (McMillan Lobby)
Session 2A: 11:00 - 12:00Session 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:30Session 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:30Session 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 ATrack B
Coffee Break: 10:30 - 11:00 (McMillan Lobby)
Session 6A: 11:00 - 12:00Session 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:30Session 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:30Session 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 ATrack B
Coffee Break: 10:30 - 11:00 (McMillan Lobby)
Session 10A: 11:00 - 12:00Session 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:30Session 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:00Session 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

Back to WADS2001 Page
Please send suggestions, comments, and notification of broken links to gs@cs.brown.edu