Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 7-9, 2001, Wyndham City Center Hotel, Washington, DC

Program Schedule


Saturday, January 6, 2001
Sunday, January 7, 2001
Sessions 1A | 1B | 1C | 2-Invited |
3A
| 3B | 3C | 4A | 4B | 4C
Monday, January 8, 2001
Sessions 5A | 5B | 5C | 6-Invited |
7A
| 7B | 7C | 8A | 8B | 8C
Tuesday, January 9, 2001
Sessions 9A | 9B | 9C | 10-Invited |
11A
| 11B | 11C | 12A | 12B | 12C
Back DA01 Home

Time Allowed for Each Presentation

Contributed Presentations: Each speaker has 20 minutes for presentation, 3 minutes for questions and 2 minutes to transfer between talks.
Invited Plenary Presentations: Each speaker has 55 minutes plus 5 minutes for questions.

The conference organizers expect every speaker of a scheduled presentation to register and attend the conference. If it becomes necessary for a speaker to cancel the presentation, the speaker is expected to find an alternate presenter immediately, preferably one of the speaker's co-authors. The speaker must inform the SIAM Conference Department immediately of any change to his/her scheduled presentation.

A "no-show" or canceled presentation can cause serious inconvenience to the attendees and conference organizers.

Saturday, January 6, 2001
6:30 PM -9:00 PM Registration Lower Lobby
6:00 PM 8:00 PM Welcome Reception

New Hampshire Ballroom

Sunday, January 7, 2001
7:30 AM - 4:30 PM Registration Lower Lobby
8:00 AM 8:50 AM Continental Breakfast Convention Foyer
9:00 AM 10:40 AM Concurrent Sessions

 

Session 1A
9:00 AM Combinatorial Approximation Algorithms for the Maximum Directed Cut Problem
Eran Halperin and Uri Zwick, Tel Aviv University, Israel
9:25 AM Approximation Algorithms for the 0-Extension Problem
Gruia Calinescu, Illinois Institute of Technology; Howard Karloff, AT&T Labs-Research and Georgia Institute of Technology; and Yuval Rabani, Technion-IIT, Israel
9:50 AM A Faster Implementation of the Goemans-Williamson Clustering Algorithm
Richard Cole, New York University; Ramesh Hariharan, Indian Institute of Science, India; Moshe Lewenstein, Bar-Ilan University and New York University; and Ely Porat, Bar-Ilan University, Israel
10:15 AM Tree Packing and Approximating k-Cuts
Joseph (Seffi) Naor and Yuval Rabani, Technion, Israel
Monticello
Session 1B
9:00 AM Generating Well-Shaped Delaunay Meshes in 3D
Xiang-Yang Li, University of Illinois at Urbana-Champaign and Illinois Institute of Technology; and Shang-Hua Teng, University of Illinois at Urbana-Champaign and Akamai Technologies
9:25 AM Approximation Algorithms for TSP with Neighborhoods in the Plane
Adrian Dumitrescu, Joseph S.B. Mitchell, University at Stony Brook
9:50 AM Dynamic Skin Triangulation
Ho-Lun Cheng, University of Illinois at Urbana-Champaign; Tamal K. Dey, Ohio State University; Herbert Edelsbrunner, Duke University; and John Sullivan, University of Illinois at Urbana-Champaign
10:15 AM Online Point Location in Planar Arrangements and Its Applications
Sariel Har-Peled, University of Illinois, Urbana; and Micha Sharir, Tel Aviv University, Israel

Potomac

Session 1C
9:00 AM Reconciling Simplicity and Realism in Parallel Disk Models
Peter Sanders, Max Planc Institut für Informatick Saarbrücken, Germany
9:25 AM Distribution Sort With Randomized Cycling
Jeffrey Scott Vitter and David A. Hutchinson, Duke University
9:50 AM External Memory BFS on Undirected Graphs with Bounded Degree
Ulrich Meyer, Max-Planck-Institut für Informatik, Germany
10:15 AM I/O-Efficient Algorithms for Graphs of Bounded Treewidth
Anil Maheshwari and Norbert Zeh, Carleton University, Ottawa, Canada
Mount Vernon
10:40 AM 11:00 AM Coffee Break

Convention Foyer

11:00 AM 12:00 PM

Session 2 -
Invited Presentation - Serving Billions of Pages to Hundreds of Millions of People is Harder Than It Seems

Yahoo! served an average of 780 million page views a day to more than 166 million unique users during September 2000. These numbers have been growing at an exponential rate for several years and are expected to continue to do so. This talk will highlight some of the non-obvious problems that we need to solve to meet this challenge.

Udi Manber, Yahoo, USA

New Hampshire Ballroom
12:00 PM 1:30 PM Luncheon

Center City I & II

1:30 PM 3:35 PM Concurrent Sessions

Session 3A
1:30 PM Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms
Noga Alon, Tel Aviv University, Israel; Benny Sudakov, Princeton University and Institute for Advanced Study; and Uri Zwick, Tel Aviv University, Israel
1:55 PM Randomized Combinatorial Algorithms for Linear Programming when the Dimension is Moderately High
M. Pellegrini, Istituto di Matematica Computazionale del CNR, Italy
2:20 PM Approximation Algorithms for the Metric Labeling Problem via a New Linear Programming Formulation
Chandra Chekuri, Bell Labs; Sanjeev Khanna, University of Pennsylvania; Joseph (Seffi) Naor, Technion, Israel; and Leonid Zosin, ITG Inc.
2:45 PM Lattice Approximation and Linear Discrepancy of Totally Unimodular Matrices
Benjamin Doerr, Christian-Albrechts-Universität zu Kiel, Germany
3:10 PM On Polynomial Approximations to the Shortest Lattice Vector Length
Ravi Kumar and D. Sivakumar, IBM Almaden Research Center
Monticello
Session 3B
1:30 PM Approximation for Minimum Triangulation of Convex Polyhedra
F.Y.L. Chin, Hong Kong University, Hong Kong; S.P.Y. Fung, Hong Kong University, Hong Kong; and C.A. Wang, Memorial University NFLD, Canada
1:55 PM Optimal Covering Tours with Turn Costs
Ester M. Arkin, Michael A. Bender, SUNY Stony Brook; Erik D. Demaine, University of Waterloo, Canada; Sandor P. Fekete, Fachbereich Mathematik TU Berlin, Germany; Joseph S.B. Mitchell, Saurabh Sethia, SUNY Stony Brook
2:20 PM Maintaining Approximate Extent of Moving Points
Pankaj K. Agarwal, Duke University; and Sariel Har-Peled, University of Illinois, Urbana
2:45 PM Simplified Kinetic Connectivity for Rectangles and Hypercubes
John Hershberger, Mentor Graphics Corporation; and Subhash Suri, University of California, Santa Barbara
3:10 PM Static and Kinetic Geometric Spanners with Applications
Menelaos I. Karavelas and Leonidas J. Guibas, Stanford University
Potomac
Session 3C
1:30 PM Gossip is Synteny: Incomplete Gossip and an Exact Algorithm for Syntenic Distance
David Liben-Nowell, MIT
1:55 PM Absolute Convergence: True Trees from Short Sequences
Tandy Warnow, University of Texas at Austin; Bernard M.E. Moret, University of New Mexico; Katherine St. John, City University of New York
2:20 PM Performance Study of Phylogenetic Methods: (Unweighted) Quartet Methods and Neighbor-Joining
Katherine St. John, City University of New York; Tandy Warnow, University of Texas at Austin; Bernard M.E. Moret, University of New Mexico; and Lisa Vawter, SmithKline Beecham
2:45 PM A Probabilistic Analysis of a Greedy Algorithm Arising from Computational Biology
Daniel G. Brown, University of Waterloo, Canada
3:10 PM On the Midpath Tree Conjecture: A Counter-Example
Rahul Shah, Rutgers University; and Martin Farach-Colton, Google Inc.
Mount Vernon
3:35 PM 4:00 PM Coffee Break Convention Foyer

4:00 PM 6:05 PM
Concurrent Sessions

Session 4A
4:00 PM Distance Labeling in Graphs
Cyril Gavoille, Université Bordeaux, France; David Peleg, The Weizmann Institute of Science, Israel; Stéphane Pérennes, Université de Nice-Sophia Antipolis, France; and Ran Raz, The Weizmann Institute of Science, Israel
4:25 PM Steiner Points in Tree Metrics Don't (Really) Help
Anupam Gupta, University of California, Berkeley
4:50 PM Fast Approximation of Centrality
David Eppstein and Joseph Wang, University of California, Irvine
5:15 PM K-Pair Delay Constrained Minimum Cost Routing in Undirected Networks
Guangting Chen, Hangzhou Institute of Electronic Engineering, Hangzhou, P.R. China; and Guoliang Xue, University of Vermont
5:40 PM A Deterministic Algorithm for the COST-DISTANCE Problem
Chandra Chekuri, Bell Labs; Sanjeev Khanna, University of Pennsylvania; and Joseph (Seffi) Naor, Technion, Israel
Monticello
Session 4B
4:00 PM Shape Sensitive Geometric Permutations
Yunhong Zhou, Washington University, St. Louis; and Subhash Suri, University of California, Santa Barbara
4:25 PM Geometric Permutations of High Dimensional Spheres
Yingping Huang, University of Notre Dame; Jinhui Xu, State University of New York at Buffalo; and Danny Z. Chen, University of Notre Dame
4:50 PM Inserting an Edge into a Planar Graph
Carsten Gutwenger, Max-Planck-Institut für Informatic, Germany; Petra Mutzel and René Weiskircher, Technische Universität Wien, Austria
5:15 PM Entropy-Preserving Cuttings and Space-Efficient Planar Point Location
Sunil Arya, Theocharis Malamatos, The Hong Kong University of Science and Technology, Hong Kong; and David M. Mount, University of Maryland, College Park
5:40 PM A Simple Entropy-Based Algorithm for Planar Point Location
Sunil Arya, Theocharis Malamatos, The Hong Kong University of Science and Technology, Hong Kong; and David M. Mount, University of Maryland, College Park
Potomac
Session 4C
4:00 PM An Experimental Study of an Opportunistic Index
Paolo Ferragina, Università di Pisa, Italy; and Giovanni Manzini, Università del Piemonte Orientale, Alessandria, Italy
4:25 PM Overlap Matching
Amihood Amir, Bar-Ilan University, Israel; Richard Cole, New York University; Ramesh Hariharan, Indian Institute of Science, India; Moshe Lewenstein and Ely Porat, Bar-Ilan University, Israel
4:50 PM A Linear Lower Bound on Index Size for Text Retrieval
Erik D. Demaine, University of Waterloo, Canada; and Alejandro López-Ortiz, University of New Brunswick, Canada
5:15 PM Pattern Matching for Sets of Segments
Alon Efrat, Piotr Indyk, Stanford University; and Suresh Venkatasubramanian, AT&T Labs - Research
5:40 PM Approximate Subset Matching with Don't Cares
Amihood Amir, Moshe Lewenstein and Ely Porat, Bar-Ilan University, Israel
6:05 PM Dynamic String Searching
Arne Andersson, Uppsala University, Sweden; and Mikkel Thorup, AT& T Labs-Research
Mount Vernon
Monday, January 8, 2001

7:30 AM - 4:30 PM

Registration

Lower Lobby

8:00 AM 8:50 AM Continental Breakfast

Convention Foyer

9:00 AM 10:40 AM
Concurrent Sessions
Session 5A
9:00 AM On Approximating the Achromatic Number
Guy Kortsarz, Open University of Israel; and Robert Krauthgamer, Weizmann Institute of Science, Israel
9:25 AM Coloring k-colorable Graphs using Smaller Palettes
Eran Halperin, Ram Nathaniel and Uri Zwick, Tel Aviv University, Israel
9:50 AM Approximating Coloring and Maximum Independent Sets in 3-uniform Hypergraphs
Michael Krivelevich, Ram Nathaniel, Tel Aviv University, Israel, and Benny Sudakov, Princeton University
10:15 AM Improved Algorithms for 3-Coloring, 3-Edge-Coloring, and Constraint Satisfaction
David Eppstein, University of California, Irvine
Monticello
Session 5B
9:00 AM Computing Optimal ±-fat and ±-small Decompositions
Mirela Damian-Iordache and Sriram V. Pemmaraju, University of Iowa
9:25 AM Optimal Planar Point Location
John Iacono, Rutgers University, New Brunswick
9:50 AM Polygonal Path Approximation with Angle Constraints
Danny Z. Chen, University of Notre Dame; Ovidiu Daescu, University of Texas at Dallas; John Hershberger, Mentor Graphics; Peter M. Kogge, University of Notre Dame; and Jack Snoeyink, University of North Carolina at Chapel Hill
10:15 AM Reconstructing a Collection of Curves with Corners and Endpoints
Stefan Funke and Edgar A. Ramos, Max-Planck-Institut für Informatic, Germany
Potomac
Session 5C
9:00 AM Web Caching using Access Statistics
Adam Meyerson, Kamesh Munagala, and Serge Plotkin, Stanford University
9:25 AM Competitive On-Line Stream Merging Algorithms for Media-on-Demand
Amotz Bar-Noy, AT&T Labs - Research; and Richard E. Ladner, University of Washington, Seattle
9:50 AM On-line Restricted Caching
Mark Brehob, Richard Enbody, Eric Torng and Stephen Wagner, Michigan State University
10:15 AM Approximate Majorization and Fair Online Load Balancing
Ashish Goel, University of Southern California, Los Angeles; Adam Meyerson and Serge Plotkin, Stanford University
Mount Vernon
10:40 AM 11:00 AM Coffee Break

Convention Foyer

11:00 AM 12:00 PM

Session 6
Invited Presentation - Game Theory, Algorithms, and the Internet

Among the many characteristics of the Internet (huge and growing, available and unstructured, dynamic and chaotic), perhaps the most novel, distinguishing, and intellectually challenging one is that, unlike previous computational artifacts and systems, the Internet is built, operated, and used by a dazzling diversity of economic interests, in various degrees of collaboration and competition with each other. Consequently, it can be argued that the mathematical arsenal necessary for attaining an algorithmic and conceptual understanding of the Internet must include some kind of fusion between mathematical economics (especially game theory and its inverse problem, mechanism design) and algorithmic thinking. In this talk I shall survey recent formalisms and results aiming in this general direction, and discuss the research agenda that appears to be emerging.

Christos Papadimitriou, University of California, Berkeley

12:00 PM 1:30 PM

Lunch (attendees are on their own)
1:30 PM 3:35 PM
Concurrent Sessions
Session 7A
1:30 PM Learning Markov Networks: Maximum Bounded Tree-Width Graphs
David Karger and Nathan Srebro, MIT
1:55 PM Approximately Covering by Cycles in Planar Graphs
Dieter Rautenbach and Bruce Reed, Université Paris, France
2:20 PM Practical Approximation Algorithms for Zero- and Bounded-Skew Trees
Alexander Z. Zelikovsky, Georgia State University; and Ion I. Mndoiu, Georgia Institute of Technology
2:45 PM Approximating the Minimum Strongly Connected Subgraph via a Matching Lower Bound
Adrian Vetta, MIT
3:10 PM Improved Approximation Algorithms for Rectangle Tiling and Packing
Piotr Berman, Pennsylvania State University; Bhaskar DasGupta, Rutgers University, Camden; S. Muthukrishnan, AT& T Labs - Research; and Suneeta Ramaswami, Rutgers University, Camden
Monticello
Session 7B
1:30 PM Secure Notarization of Paper Text Documents
Matthias Ruhl, MIT; Marshall Bern and David Goldberg, Xerox PARC
1:55 PM Sublinear Time Approximate Clustering
Nina Mishra, Hewlett-Packard Labs; Dan Oblinger, IBM TJ Watson Labs; and Leonard Pitt, University of Illinois at Urbana-Champaign
2:20 PM Efficient Oblivious Transfer Protocols
Moni Naor, Weizmann Institute of Science, Israel; and Benny Pinkas, Intertrust Technologies
2:45 PM Constructing Pseudo-Random Permutations with a Prescribed Structure
Moni Naor, Weizmann Institute of Science, Israel; and Omer Reingold, AT&T Labs Research
3:10 PM Robust Algorithms for Restricted Domains
Vijay Raghavan and Jeremy Spinrad, Vanderbilt University
Potomac
Session 7C
1:30 PM Polynomial Algorithms for Partitioning Problems on Graphs with Fixed Clique-width
Daniel Kobler, Fields Institute for Research in Mathematical Sciences, Canada; and Udi Rotics, University of Toronto, Canada
1:55 PM A Polynomial Time Recognition Algorithm for Probe Interval Graphs
Julie L. Johnson and Jeremy P. Spinrad, Vanderbilt University
2:20 PM Colored Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width
J.A. Makowsky, Technion-Israel Institute of Technology, Israel
2:45 PM A New Constructive Root Bound for Algebraic Expressions
Chen Li and Chee Yap, New York University
3:10 PM Orderly Spanning Trees with Applications to Graph Encoding and Graph Drawing
Yi-Ting Chiang, Ching-Chi Lin and Hsueh-I Lu, Institute of Information Science, Academia Sinica, Taiwan
Mount Vernon

3:35 PM 4:00 PM

Coffee Break

Convention Foyer

4:00 PM 6:05 PM
Concurrent Sessions
Session 8A
4:00 PM Alternatives to Splay Trees with O(log n) Worst-case Access Times
John Iacono, Rutgers University, New Brunswick
4:25 PM Worst Case Constant Time Priority Queue
Andrej Brodnik, Institute of Mathematics, Physics, and Mechanics, Ljubljana, Slovenia and Luleå University of Technology, Sweden; Svante Carlsson, Luleå University of Technology, Sweden; Johan Karlsson, Luleå University of Technology, Sweden; and J. Ian Munro, University of Waterloo, Canada
4:50 PM Representing Dynamic Binary Trees Succinctly
J. Ian Munro, University of Waterloo, Canada; Venkatesh Raman, Institute of Mathematical Sciences, Chennai, India; and Adam J. Storm, University of Waterloo, Canada
5:15 PM Making Data Structures Confluently Persistent
Amos Fiat and Haim Kaplan, Tel Aviv University, Israel
5:40 PM Compact Labeling Schemes for Ancestor Queries
Serge Abiteboul, INRIA-Rocquencourt, France; Haim Kaplan and Tova Milo, Tel Aviv University, Israel
Monticello
Session 8B
4:00 PM Better Approximation Algorithms for Bin Covering
Janos Csirik, University of Szeged, Hungary; David S. Johnson, AT& T Labs; and Claire Kenyon, Université Paris-Sud, France
4:25 PM New Approaches to Covering and Packing Problems
Aravind Srinivasan, Bell Laboratories, Lucent Technologies
4:50 PM Parallel Processor Scheduling with Delay Constraints
Daniel W. Engels, Jon Feldman, David R. Karger and Matthias Ruhl, MIT
5:15 PM Approximation Algorithms for Extensible Bin Packing
E.G. Coffman, Jr., Columbia University; and George S. Lueker, University of California, Irvine
5:40 PM Scheduling Precedence-Constrained Jobs with Stochastic Processing Times on Parallel Machines
Martin Skutella and Marc Uetz, Technische Universität Berlin, Germany
Potomac
Session 8C
4:00 PM Loss-Bounded Analysis for Differentiated Services
Alexander Kesselman, Check Point Software Technologies and Tel Aviv University, Israel; and Yishay Mansour, Tel Aviv University, Israel
4:25 PM Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds
Allan Borodin, University of Toronto, Canada; Rafail Ostrovsky, Telcordia Technologies; and Yuval Rabani, IIT, Israel
4:50 PM Distributed Admission Control, Scheduling, and Routing with Stale Information
Ashish Goel, University of Southern California, Los Angeles; Adam Meyerson and Serge Plotkin, Stanford University
5:15 PM On Algorithms for Efficient Data Migration
Joseph Hall, Jason Hartline, Anna R. Karlin, Jared Saia, University of Washington, Seattle; and John Wilkes, Hewlett-Packard Research Laboratories
5:40 PM Fast Distributed Graph Coloring with O(”) Colors
Gianluca De Marco, Università di Salerno, Italy and Andrzej Pelc, Université du Québec a Hull, Canada
Mount Vernon
6:15 PM 7:15 PM

SIAM Business Meeting

Potomac

Tuesday, January 9, 2001

7:30 AM - 11:00 AM Registration

Lower Lobby

8:00 AM 8:50 AM

Continental Breakfast

Convention Foyer

9:00 AM 10:40 AM
Concurrent Sessions
Session 9A
9:00 AM Improved Algorithms for Fault Tolerant Facility Location
Sudipto Guha, AT&T Shannon Labs; Adam Meyerson and Kamesh Munagala, Stanford University
9:25 AM Algorithms for Facility Location Problems with Outliers
Moses Charikar, Stanford University; Samir Khuller, David M. Mount, University of Maryland, College Park; and Giri Narasimhan, University of Memphis
9:50 AM The Probabilistic Relationship between the Assignment and Asymmetric Traveling Salesman Problems
Alan Frieze, Carnegie Mellon University; and Gregory B. Sorkin, IBM T.J. Watson Center
10:15 AM Approximation Algorithms for Data Placement in Arbitrary Networks
Ivan D. Baev and Rajmohan Rajaraman, Northeastern University
Monticello
Session 9B
9:00 AM Polynomial-Time Approximation Schemes for Geometric Graphs
Thomas Erlebach, Computer Engineering and Networks Laboratory, Switzerland; Klaus Jansen and Eike Seidel Christian-Albrechts-University of Kiel, Germany
9:25 AM Morphing between Polylines
Alon Efrat, The University of Arizona; Sariel Har-Peled, Duke University; Leonidas J. Guibas, Stanford University and T.M. Murali, Compaq Computer Corporation
9:50 AM Fast Implementation of Depth Contours using Topogical Sweep
Kim Miller, Tufts University; Suneeta Ramaswami, Rutgers University, Camden; Peter Rousseeuw, U.I.A., Belgium; Toni Sellarès, Universitat de Girona, Spain; Diane Souvaine, Tufts University; Ileana Streinu, Smith College; and Anja Struyf, U.I.A., Belgium
10:15 AM Computing the Depth of a Flat
Marshall Bern, Xerox PARC; and David Eppstein, University of California, Irvine
Potomac
Session 9C
9:00 AM Which Formulae Shrink Under Random Restrictions?
Hana Chockler, The Hebrew University, Israel; and Uri Zwick, Tel Aviv University, Israel
9:25 AM Selective Families, Superimposed Codes, and Broadcasting on Unknown Radio Networks
Andrea E.F. Clementi, Università di Roma "Tor Vergata", Italy; Angelo Monti, Università "La Sapienza" di Roma, Italy; and Riccardo Silvestri, Università de L'Aquila, Italy
9:50 AM Adversarial Models in Evolutionary Game Dynamics
G. Istrate, M.V. Marathe,Los Alamos National Laboratory; and S.S. Ravi, SUNY at Albany
10:15 AM The Phase Transition in 1-in-k SAT and NAE 3-SAT
Dimitri Achlioptas, Microsoft Research; Arthur Chtcherba, University of New Mexico; Gabriel Istrate, Los Alamos National Laboratory; and Cristopher Moore, University of New Mexico
Mount Vernon
10:40 AM 11:00 AM Coffee Break

Convention Foyer

11:00 AM 12:00 PM

Session 10
Invited Presentation - Guessing Secrets

We consider a variant of the familiar "20 questions" problem in which one tries to discover the identity of some unknown "secret" by asking binary questions. In this variation, there is now a set of two (or more) secrets. For each question asked, an adversary gets to choose which of the secrets to use in supplying the answer, which in any case must be truthful. We will describe a number of algorithms for dealing with this problem, although we are still far from a complete understanding of the situation. Problems of this type have recently arisen in connection with certain Internet traffic routing applications.

Ronald L. Graham, University of California, San Diego, USA

New Hampshire Ballroom
12:00 PM 1:45 PM Lunch (attendees on their own)

1:45 PM 3:50 PM
Concurrent Sessions

Session 11A
1:45 PM Can Entropy Characterize Performance of Online Algorithms?
Gopal Pandurangan and Eli Upfal, Brown University
2:10 PM Competitive Auctions and Digital Goods
Andrew V. Goldberg, InterTrust Technologies Corporation; Jason D. Hartline, University of Washington; and Andrew Wright, InterTrust Technologies Corporation
2:35 PM Towards Understanding the Predictability of Stock Markets from the Perspective of Computational Complexity
James Aspnes, Yale University; David F. Fischer, Yale College; Michael J. Fischer, Ming-Yang Kao and Alok Kumar, Yale University
3:00 PM Performance Guarantee for Online Deadline Scheduling in the Presence of Overload
Tak-Wah Lam and Kar-Keung To, University of Hong Kong, Hong Kong
Cancelled 3:25 PM Assigning Chain-like Tasks to a Chain-like Network
Gerhard J. Woeginger, Institut für Mathematick B, TU Graz, Austria
Monticello
Session 11B
1:45 PM The Inverse Nearest Neighbor Problem with Astrophysical Applications
Richard Anderson and Brian Tjaden, University of Washington
2:10 PM Reductions Among High Dimensional Proximity Problems
Ashish Goel, University of Southern California; Piotr Indyk, MIT; and Kasturi Varadarajan, University of Iowa
2:35 PM A Cell Probe Lower Bound for Dynamic Nearest-neighbour Searching
Stephen Alstrup, IT University of Copenhagen, Denmark; Thore Husfeldt, Lund University, Sweden; and Theis Rauhe, IT University of Copenhagen, Denmark
3:00 PM Shape Matching using Edit-distance: An Implementation
Philip N. Klein, Thomas B. Sebastian and Benjamin B. Kimia, Brown University
3:25 PM On Validating Planar Worlds
Vida Dujmovic; and Sue Whitesides, McGill University, Canada
Potomac
Session 11C
1:45 PM Improved Fast Integer Sorting in Linear Space
Yijie Han, University of Missouri at Kansas City
2:10 PM Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time
Ulrich Meyer, Max-Planck-Institut für Informatik, Germany
2:35 PM Optimal Constrained Graph Exploration
Christian A. Duncan, University of Miami; Stephen G. Kobourov, University of Arizona; and V. S. Anil Kumar, Max-Planck-Institut für Informatick, Germany
3:00 PM An Efficient Algorithm for the Configuration Problem of Dominance Graphs
Ernst Althaus, Max-Planck-Institute for Computer Science, Germany; Denys Duchier, Alexander Koller, Universität des Saarlandes, Germany; Kurt Mehlhorn, Max-Planck-Institute for Computer Science, Germany; Joachim Niehren, Universität des Saarlandes, Germany; and Sven Thiel, Max-Planck-Institute for Computer Science, Germany
3:25 PM Linear Reductions of Maximum Matching
Therese Biedl, University of Waterloo, Canada
Mount Vernon
3:50 PM 4:15 PM Coffee Break Convention Foyer

4:15 PM 6:20 PM
Concurrent Sessions

Session 12A
4:15 PM Internet Packet Filter Management and Rectangle Geometry
David Eppstein, University of California, Irvine; and S. Muthukrishnan, AT&T Labs
4:40 PM Faster Kinetic Heaps and Their Use in Broadcast Scheduling
Haim Kaplan, Tel Aviv University, Israel; Robert E. Tarjan, InterTrust Technologies and Princeton University; and Kostas Tsioutsiouliklis, Princeton University
5:05 PM Finding Least Common Ancestors in Directed Acyclic Graphs
Michael A. Bender, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin, State University of New York at Stony Brook
5:30 PM On Binary Searching with Non-Uniform Costs
Eduardo S. Laber, PESC/COPPE, Universidade Federal do Rio de Janeiro, Brazil; and Ruy L. Milidiú, Artur A. Pessoa, Departamento de Informática, PUC-Rio, Brazil
5:55 PM Soft Kinetic Data Structures
Artur Czumaj, New Jersey Institute of Technology; and Christian Sohler, University of Paderborn, Germany
Monticello
Session 12B
4:15 PM Testing Graphs for Colorability Properties
Eldar Fischer, NEC Research Institute
4:40 PM Random Lifts of Graphs
Alon Amit; Nathan Linial; Jiri Matousek; and Eyal Rozenman
5:05 PM Improved Results for Route Planning in Stochastic Transportation Networks
Justin Boyan, NASA Ames Research Center; and Michael Mitzenmacher, Harvard University
5:30 PM Hill-Climbing Finds Random Planted Bisections
Ted Carson and Russell Impagliazzo, University of California, San Diego
5:55 PM On Universally Easy Classes for NP-complete Problems
Erik D. Demaine, University of Waterloo, Canada; Alejandro López-Ortiz, University of New Brunswick, Canada; and J. Ian Munro, University of Waterloo, Canada
Potomac
Session 12C
4:15 PM The Diameter of Random Massive Graphs
Linyuan Lu, University of California, San Diego
4:40 PM Domatic Partitions and the Lovász Local Lemma
Aravind Srinivasan, Bell Laboratories, Lucent Technologies
5:05 PM Equitable Colorings Extend Chernoff-Hoeffding Bounds
Sriram V. Pemmaraju, The University of Iowa
5:30 PM Universal Configurations in Light-Flipping Games
Yevgeniy Dodis, MIT; and Peter Winkler, Bell Labs
5:55 PM On the Discrete Bak-Sneppen Model of Self-organized Criticality
Jérémy Barbay and Claire Kenyon, Université Paris-Sud, France
Mount Vernon
6:20 PM Conference Adjourns

©2000, Society for Industrial and Applied Mathematics
Designed by Donaghy's Web Consulting
Created 11/20/00; Updated 1/02/01