SIAM Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, Radisson Miyako Hotel, San Francisco, CA

Full Technical Program

Sat, January 5, 2002    
4:00 PM-8:00 PM Registration Pre-Function Area
6:00 PM-8:00 PM Welcome Reception Imperial Ballroom
Sun, January 6, 2002    
7:30 AM-4:30 PM Registration Pre-Function Area
8:00 AM-8:50 AM Continental Breakfast Pre-Function Area
Concurrent Sessions
9:00 AM-11:05 AM
Session 1A
9:00 AM Static Optimality and Dynamic Search-Optimality in Lists and Trees
Avrim Blum, Shuchi Chawla and Adam Kalai, Carnegie Mellon University
9:25 AM Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting
Rasmus Pagh, University of Aarhus, Denmark; and Jakob Pagter, CRYPTOMAThIC
9:50 AM Union-find with Deletions
Haim Kaplan and Nira Shafrir, Tel Aviv University, Israel; and Robert E. Tarjan, Princeton University
10:15 AM A Locality-Preserving Cache-Oblivious Dynamic Dictionary
Michael A. Bender and Ziyang Duan, State University of New York; John Iacono, Polytechnic University; and Jing Wu, State University of New York
10:40 AM Cache Oblivious Search Trees via Binary Trees of Small Height
Gerth S. Brodal, Rolf Fagerberg and Riko Jacob, University of Aarhus, Denmark
Imperial A
Session 1B
9:00 AM An Approximation Algorithm for the Group Steiner Problem
Guy Even, Tel-Aviv University, Israel; and Guy Kortsarz, Rutgers University
9:25 AM On Directed Steiner Trees
Leonid Zosin, ITG Inc; and Samir Khuller, University of Maryland at College Park
9:50 AM An 8/13-Approximation Algorithm for the Asymmetric Maximum TSP
Markus Bläser, Universität zu Lübeck, Germany
10:15 AM Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems
Béla Csaba, Max-Planck-Institut für Informatik; Marek Karpinski, University of Bonn; and Piotr Krysta, Max-Planck-Institut für Informatik, Germany
10:40 AM An Ear Decomposition Approach to Approximating the Smallest 3-Edge Connected Spanning Subgraph of a Multigraph
Harold N. Gabow, University of Colorado
Imperial B
Session 1C
9:00 AM Censorship Resistant Peer-to-Peer Content Addressable Networks
Amos Fiat, Tel Aviv University, Israel; and Jared Saia, University of Washington
9:25 AM Web Caching with Request Reordering
Tomás Feder and Rajeev Motwani, Stanford University; Rina Panigrahy, Cisco; and An Zhu, Stanford University
9:50 AM Improved Algorithms for the Data Placement Problem
Sudipto Guha, AT&T Shannon Labs; and Kamesh Munagala, Stanford University
10:15 AM Undiscretized Dynamic Programming: Faster Algorithms for Facility Location and Related Problems on Trees
Rahul Shah and Martin Farach-Colton, Rutgers University
10:40 AM Temporary Tasks Assignment Resolved
Amitai Armon and Yossi Azar, Tel Aviv University, Israel; Leah Epstein, The Interdisciplinary Center, Israel; and Oded Regev, Institute for Advanced Study
Spring B/C
11:05 AM - 11:30 AM Coffee Break Pre-Function Area
Plenary Session
11:30 AM-12:30 PM

Session 2
The Theory Behind LEDA

LEDA is a widely used platform for combinatorial and geometric computing. Its distinguishing features are: wide scope, ease of use, correctness, and efficiency. After a short overview of the library, I will discuss some of the theoretical work underlying the system: program checking, exact number types and exact geometry kernels, new algorithms, analysis of arithmetic demand, and exploration of design choices.

Kurt Mehlhorn, Max-Planck-Institut für Informatik, Germany

Imperial Ballroom

Concurrent Sessions
2:00 PM-4:05 PM

Session 3A
2:00 PM Dense Point Sets Have Sparse Delaunay Triangulations
Jeff Erickson, University of Illinois at Urbana-Champaign
2:25 PM Delaunay Triangulation Programs on Surface Data
Sunghee Choi and Nina Amenta, The University of Texas at Austin
2:50 PM Quality Meshing with Weighted Delaunay Refinement
Siu-Wing Cheng, Hong Kong University of Science and Technology; and Tamal K. Dey, Ohio State University
3:15 PM Linear-Size Approximate Voronoi Diagrams
Sunil Arya and Theocharis Malamatos, Hong Kong University of Science and Technology
3:40 PM Motorcycle Graphs and Straight Skeletons
Siu-Wing Cheng and Antoine Vigneron, Hong Kong University of Science and Technology
Imperial A
Session 3B
2:00 PM Faster Approximation Schemes for Fractional Multicommodity Flow Problems
George Karakostas, Telcordia Technologies, Inc.
2:25 PM Flows Over Time With Load-Dependent Transit Times
Ekkehard Köhler and Martin Skutella, Technische Universität, Berlin
2:50 PM Improved Bounds for the Unsplittable Flow Problem
Petr Kolman, Charles University, Czech Republic; and Christian Scheideler, Johns Hopkins University
3:15 PM NP - Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow
Thomas Erlebach and Alexander Hall, Computer Engineering and Networks Laboratory, Switzerland
3:40 PM How Unfair is Optimal Routing?
Tim Roughgarden, Cornell University
Imperial B
Session 3C
2:00 PM Approximation Algorithms for Grammar-Based Compression
Eric Lehman and Abhi Shelat, Massachusetts Institute of Technology
2:25 PM Improving Table Compression with Combinatorial Optimization
Adam L. Buchsbaum and Glenn S. Fowler, AT&T Shannon Labs; and Raffaele Giancarlo, Universitá di Palermo, Italy
2:50 PM Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of Bits
Hsueh-I Lu, Institute of Information Science, Taiwan
3:15 PM Succinct Representations of lcp Information and Improvements in the Compressed Suffix Arrays
Kunihiko Sadakane, Tohoku University, Japan
3:40 PM Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets
Rajeev Raman, University of Leicester, UK; Venkatesh Raman and S. Srinivasa Rao, Institute of Mathematical Sciences, India
Spring B/C

4:05 PM-4:30 PM

Coffee Break Pre-Function Area

Concurrent Sessions
4:30 PM-6:35 PM

Session 4A
4:30 PM Jenga
Uri Zwick, Tel Aviv University, Israel
4:55 PM Guessing Secrets with Inner Product Questions
Fan Chung, Ronald Graham and Linyuan Lu, University of California
5:20 PM Guessing Secrets Efficiently via List Decoding
Noga Alon, Tel Aviv University, Israel; Venkatesan Guruswam, University of California at Berkeley; Tali Kaufman, Tel Aviv University; and Madhu Sudan, Massachusetts Institute of Technology
5:45 PM How to Cut a Cake Almost Fairly
Sven O. Krumke, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Germany; Maarten Lipmann and Willem E. de Paepe, Technical University of Eindhoven, Netherlands; Diana Poensgen and Jörg Rambau, Konrad-Zuse-Zentrum für Informationstechnik Berlin; Leen Stougie, Technical University of Eindhoven; and Gerhard J. Woeginger, University of Twente, Netherlands
6:10 PM The Mathematics of Playing Golf
Giovanni Rinaldi, Istituto di Analisi dei Sisstemi e Informatica, Roma, Italy, Ulrich Voigt, Universität Freiburg, Germany and Gerhard.J. Woeginger, University of Twente, Netherlands
Imperial A
Session 4B
4:30 PM Computing Shortest Paths with Comparisons and Additions
Seth Pettie and Vijaya Ramachandran, The University of Texas at Austin
4:55 PM An Optimal Algorithm for Checking Regularity
Y. Kohayakawa, Universidade de São Paulo, Brazil; V. Rödl, Emory University; and L. Thoma, University of Rhode Island
5:20 PM Edge Dominating and Hypomatchable Sets
Ojas Parekh, Carnegie Mellon University
5:45 PM An Algorithm for Counting Maximum Weighted Independent Sets and its Applications
Vilhelm Dahllöf and Peter Jonsson, Linköping University, Sweden
6:10 PM Algorithms for Quantified Boolean Formulas
Ryan Williams, Cornell University
Imperial B
Session 4C
4:30 PM Balls and Bins Models with Feedback
Eleni Drinea, Harvard University; Alan Frieze, Carnegie Mellon University; and Michael Mitzenmacher, Harvard University
4:55 PM A Note on Random 2-SAT with Prescribed Literal Degrees
Colin Cooper, University of London; Alan Frieze, Carnegie Mellon University; and Gregory B. Sorkin, Watson Research Center
5:20 PM Mixing Time and Long Paths in Graphs
Igor Pak, Massachusetts Institute of Technology
5:45 PM The Diameter of a Long Range Percolation Graph
Don Coppersmith, David Gamarnik and Maxim Sviridenko, T. J. Watson Research Center
6:10 PM Is the Internet Fractal?
Cedric Adjih, Rocquencourt, France; Leonidas Georgiadis, Aristotle University, Greece; Philippe Jacquet, Rocquencourt; and Wojciech Szpankowski, Purdue University
Spring B/C
Mon, January 7, 2002    
7:30 AM-4:30 PM Registration Pre-Function Area
8:00 AM-8:50 AM

Continental Breakfast

Pre-Function Area

Concurrent Sessions
9:00 AM-11:05 AM

Session 5A
9:00 AM Center and Diameter Problems in Plane Triangulations and and Quadrangulations
Victor Chepoi, Université Aix-Marseille II, France; Feodor Dragan, Kent State University; and Yann Vaxès, Université Aix-Marseille II
9:25 AM Symmetric Drawings of Triconnected Planar Graphs
Seok-Hee Hong, University of Sydney, Australia; Brendan McKay, Australian National University; and Peter Eades, University of Sydney
9:50 AM Layout Area of the Hypercube
Shimon Even and Roni Kupershtok, Israel Institute of Technology
10:15 AM I/O-Optimal Algorithms for Planar Graphs Using Separators
Anil Maheshwari and Norbert Zeh, Carleton University, Canada
10:40 AM Polynomial Time Recognition of P4-structure
R. B. Hayward, University of Alberta, Canada; S. Hougardy, Humboldt-Universität ze Berlin, Germany; and B.A. Reed, McGill University, Canada
Imperial A
Session 5B
9:00 AM Adaptive Intersection and t-Threshold Problems
Jérémy Barbay and Claire Kenyon, Université Paris-Sud, France
9:25 AM Separable Attributes: A Technique for Solving the Sub Matrices Character Count Problem
Amihood Amir and Kenneth W. Church, AT&T Shannon Labs; and Emanuel Dar, Bar-Ilan University, Israel
9:50 AM Tiling Groups for Wang Tiles
Cristopher Moore, University of New Mexico and the Santa Fe Institute; Ivan Rapaport, Universidad de Chile; and Eric Rémila, École Normale Supérieure de Lyon, France
10:15 AM Generating Random Factored Numbers, Easily
Adam Kalai, Massachusetts Institute of Technology
Imperial B
Session 5C
9:00 AM Tight Bounds for Worst-Case Equilibria
Artur Czumaj, New Jersey Institute of Technology; and Berthold Vöcking, Max-Planck-Institut für Informatik, Germany
9:25 AM Broadcast Scheduling: When Fairness is Fine
Jeff Edmonds, York University, Canada; and Kirk Pruhs, Univeristy of Pittsburgh
9:50 AM Harmonic Broadcasting is Optimal
Lars Engebretsen, Royal Institute of Technology, Swecden and Madhu Sudan, Massachusetts Institute of Technology
10:15 AM Windows Scheduling Problems for Broadcast Systems
Amotz Bar-Noy, AT&T Shannon Labs; and Richard E. Ladner, University of Washington
10:40 AM Scheduling Protocols for Switches with Large Envelopes
Matthew Andrews and Lisa Zhang, Bell Labs
Spring B/C
11:05 AM-11:30 AM Coffee Break Pre-Function Area
Plenary Session
11:30 AM-12:30 PM

Session 6
The Virtues of Expanding Geometric Objects

A natural question in motion planning is concerned with, for example, how to manipulate a robot arm from one given configuration to another. Although, in general, this can be essentially intractable, there are certain natural instances which are tractable. Consider the case when the arm is a polygonal chain embedded in the plane with no crossings. The problem is to continuously open the chain remaining in the plane and to straighten it without creating any crossings or changing any link length. The key idea, first suggested by Gunter Rote, is to look for a motion that expands the distances between every nonadjacent pair of vertices of the chain. The key technique, which supplies the straightening algorithm, comes from the theory of frameworks and tensegrity structures.

Bob Connelly, Cornell University

Imperial Ballroom

Concurrent Sessions
2:00 PM-4:05 PM

Session 7A
2:00 PM Covering Shapes by Ellipses
Alon Efrat, University of Arizona; Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, and Carola Wenk, Freie Universität Berlin, Germany
2:25 PM Slice and Dice: A Simple, Improved, Approximation Tiling Recipe
Piotr Berman, Pennsylvania State University, Bhaskar DasGupta, University of Illinois at Chicago, and S. Muthukrishnan, AT&T Labs - Research
2:50 PM Binary Space Partitions for Line Segments with a Limited Number of Directions
Csaba David Tóth, Institute for Theoretical Computer Science, Switzerland
3:15 PM Closest-Point Problems Simplified on the RAM
Timothy M. Chan, University of Waterloo, Canada
3:40 PM Semi-Online Maintenance of Geometric Optima and Measures
Timothy M. Chan, University of Waterloo, Canada
Imperial A
Session 7B
2:00 PM Generalized Clustering
Sudipto Guha, AT&T Shannon Labs; and Kamesh Munagala, Stanford University
2:25 PM New Bounds for Multi-Dimensional Packing
Steven S. Seiden, Louisiana State University; and Rob van Stee, Freiburg University, Germany
2:50 PM Computer Assisted Proof of Optimal Approximability Results
Uri Zwick, Tel-Aviv University, Israel
3:15 PM MAX CUT in Cubic Graphs
Eran Halperin, Dror Livnat and Uri Zwick, Tel-Aviv University, Israel
3:40 PM Approximating Minimum Unsatisfiability of Linear Equations
Piotr Berman, Pennsylvania State University; and Marek Karpinski, University of Bonn, Germany
Imperial B
Session 7C
2:00 PM On-Line Algorithms for the Dynamic Traveling Repair Problem
Sandy Irani, Xiangwen Lu and Amelia Regan, University of California at Irvine
2:25 PM Competitive On-line Switching Policies
Amotz Bar-Noy, AT&T Shannon Labs; Ari Freund, Shimon Landa and Joseph (Seffi) Naor, Technion, Israel
2:50 PM A Randomized Online Algorithm for Bandwidth Utilization
Sanjeev Arora and Bo Brinkman, Princeton University
3:15 PM Caching with Expiration Times
Parikshit Gopalan, Georgia Institute of Technology; Howard Karloff, AT&T Research Labs; Aranyak Mehta, Milena Mihail and Nisheeth Vishnoi, Georgia Institute of Technology
3:40 PM On-Line Scheduling of a Single Machine to Minimize Total Weighted Completion Time
E. J. Anderson, University of New South Wales, Sydney; and C. N. Potts, University of Southhampton, United Kingdom
Spring B/C
4:05 PM-4:30 PM Coffee Break Pre-Function Area

Concurrent Sessions
4:30 PM-6:10 PM

Session 8A
4:30 PM Hardware-Assisted Computation of Depth Contours
Shankar Krishnan, AT&T Research Labs; Nabil Mustafa, Duke University; and Suresh Venkatasubramanian, AT&T Research Labs
4:55 PM The Freeze-Tag Problem: How to Wake Up a Swarm of Robots
Esther M. Arkin and Michael A. Bender, SUNY Stony Brook; Sándor P. Fekete, Technische Universität Braunschweig; Joseph S. B. Mitchell, SUNY Stony Brook; and Martin Skutella, Technische Universität Berlin
5:20 PM The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem
Darin Goldstein, California State at Fullerton; and Nick Meyer, University of California at Berkeley
5:45 PM Tree Exploration with Little Memory
Krzysztof Diks, Uniwersytet Warszawski, Poland; Pierre Fraigniaud, Université Paris-Sud, France; Evangelos Kranakis, Carleton University, Canada; and Andrzej Pelc, Université du Québec à Hull, Canada
Imperial A
Session 8B
4:30 PM Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms
Irene Finocchi, Alessandro Panconesi and Riccardo Silvestri, Università di Roma, Italy
4:55 PM On Semidefinite Programming Relaxations for Graph Coloring and Vertex Cover
Moses Charikar, Princeton University
5:20 PM Approximating k-cuts via Network Strength
R. Ravi and Amitabh Sinha, Carnegie Mellon University
Imperial B
Session 8C
4:30 PM Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs
Ziv Bar-Yossef, University of California at Berkeley; Ravi Kumar and D. Sivakumar, IBM Almaden Research Center
4:55 PM Sampling From a Moving Window Over Streaming Data
Brian Babcock, Mayur Datar and Rajeev Motwani, Stanford University
5:20 PM Maintaining Stream Statistics over Sliding Windows
Mayur Datar and Aristides Gionis, Stanford University; Piotr Indyk, Massachusetts Institute of Technolgy; and Rajeev Motwani, Stanford University
5:45 PM Testing Satisfiability
Noga Alon and Asaf Shapira, Tel Aviv University, Israel
Spring B/C

6:15 PM - 7:15 PM

SODA Business Meeting  
Tues, January 8, 2002    
7:30 AM - 11:00 AM


Pre-Function Area
7:30 AM - 8:00 AM Continental Breakfast Pre-Function Area

Concurrent Sessions
8:00 AM - 10:05 AM

Session 9A
8:00 AM Efficient Pattern-Matching with Don't Cares
Adam Kalai, Massachusetts Institute of Technology
8:25 AM Efficient Algorithms for Document Retrieval Problems
S. Muthukrishnan, AT&T Research Labs
8:50 AM The String Edit Distance Matching Problem with Moves
Graham Cormode, University of Warwick, UK; and S. Muthukrishnan, AT&T Research Labs
9:15 AM Simple Approximation Algorithm for Nonoverlapping Local Alignments
Piotr Berman, Pennsylvania State University; Bhaskar Dasgupta, University of Illinois at Chicago; and S. Muthukrishnan, AT&T Research Labs
9:40 AM A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost Matrices
Maxime Crochemore, Universit de Marne-la-Valée, France; Gad M. Landau and Michal Ziv-Ukelson, Haifa University, Israel
Imperial A
Session 9B
8:00 AM On Adaptive Deterministic Gossiping in ad hoc Radio Networks
Leszek Gasieniec, University of Liverpool, UK; and Andrzej Lingas, Lund University, Sweden
8:25 AM Expansion of Product Replacement Graphs
Alexander Gamburd, Stanford University; and Igor Pak, Massachusetts Institute of Technology
8:50 AM Explicit Constructions of Selectors and Related Combinatorial Structures, with Applications
Piotr Indyk, Massachusetts Institute of Technology
9:15 AM Derandomized Dimensionality Reduction with Applications
Lars Engebretsen, Royal Institute of Technology; Piotr Indyk and Ryan O'Donnell, Massachusetts Institute of Technology
9:40 AM Minimizing Randomness in Minimum Spanning Tree, Parallel Connectivity, and Set Maxima Algorithms
Seth Pettie and Vijaya Ramachandran, The University of Texas at Austin
Imperial B
Session 9C
8:00 AM Existence Theorems, Lower Bounds and Algorithms for Scheduling to Meet Two Objectives
April Rasala, Massachusetts Institute of Technology; Cliff Stein, Columbia University; Eric Torng, Michigan State University; and Patchrawat Uthaisombut, University of Pittsburgh
8:25 AM Scheduling Split Intervals
Reuven Bar-Yehuda, Technion; Magnús M. Halldórsson, Iceland Genomics Corporation; Joseph (Seffi) Naor, Hadas Shachnai, and Irina Shapira, Technion
8:50 AM Throughput Maximization of Real-Time Scheduling with Batching
Amotz Bar-Noy, AT&T Shannon Laboratory; Sudipto Guha, University of Pennsylvania; Yoav Katz and Joseph (Seffi) Naor, Technion, Israel; Baruch Schieber, IBM T.J. Watson Research Center; and Hadas Shachnai, Lucent Technologies
9:15 AM (Incremental) Priority Algorithms
Allan Borodin, University of Toronto, Canada; Morten N. Nielsen, University of Southern Denmark; and Charles Rackoff, University of Toronto
9:40 AM Improved Algorithms for Stretch Scheduling
Michael A. Bender, SUNY at Stony Brook; S. Muthukrishnan, AT&T Shannon Laboratory; and Rajmohan Rajaraman, Northeastern University
Spring B/C
10:05 AM - 10:30 AM Coffee Break Pre-Function Area

Concurrent Sessions
10:30 AM - 12:35 PM

Session 10A
10:30 AM Shape Dimension and Approximation from Samples
Tamal K. Dey, Joachim Giesen, Samrat Goswami and Wulue Zhao, Ohio State University
10:55 Smooth-Surface Reconstruction in Near-Linear Time
Stefan Funke and Edgar A. Ramos, Max-Planck-Institut für Informatik, Germany
11:20 AM Computing the Writhing Number of a Polygonal Knot
Pankaj K. Agarwal, Herbert Edelsbrunner, and Yusu Wang, Duke University
11:45 AM Pseudo-Line Arrangements: Duality, Algorithms, and Applications
Pankaj K. Agarwal, Duke University; and Micha Sharir, Tel Aviv University, Israel
12:10 PM On the Overlay of Envelopes in Four Dimensions
Vladlen Koltun and Micha Sharir, Tel Aviv University, Israel
Imperial A
Session 10B
10:30 AM Preprocessing an Undirected Planar Network to Enable Fast
Philip N. Klein, Brown University
10:55 AM Approximate Distance Oracles for Geometric Graphs
Joachim Gudmundsson, Utrecht University, Netherlands; Christos Levcopoulos, Lund University, Sweden; Giri Narasimhan, Florida Internation University; and Michiel Smid, Carleton University, Canada
11:20 AM Oracles for Distances Avoiding a Link-failure
Camil Demetrescu, Università di Roma, Italy; and Mikkel Thorup, AT&T Research Laboratories
11:45 AM Roundtrip Spanners and Roundtrip Routing in Directed Graphs
Liam Roditty, Tel Aviv University, Israel; Mikkel Thorup, AT&T Research Laboratories; and Uri Zwick, Tel Aviv University
12:10 PM Light Spanners and Approximate TSP in Weighted Graphs with Forbidden Minors
Michelangelo Grigni and Papa Sissokho, Emory University
Imperial B
Session 10C
10:30 AM Capacitated Vertex Covering with Applications
Sudipto Guha, University of Pennsylvania; Refael Hassin, Tel Aviv University, Israel; Samir Khuller, University of Maryland at College Park; and Einat Or, Tel Aviv University
10:55 AM Construction of Probe Interval Models
Ross M. McConnell, University of Colorado at Denver; and Jeremy P. Spinrad, Vanderbilt University
11:20 AM A New Algorithm for Protein Folding in the HP Model
Alantha Newman, Massachusetts Institute of Technology
11:45 AM An Optimal (Expected Time) Algorithm for Minimizing Lab Costs in DNA Sequencing
David Hart,University of California at Irvine
12:10 PM Approximating Minimum Quartet Inconsistency
Gianluca Della Vedova, Università degli Studi di Milano-Bicocca, Italy; Tao Jiang, Jing Li, and Jianjun Wen, University of California at Riverside
Spring B/C
12:35 PM - 2:00 PM Lunch Break Attendees on their own.

Concurrent Sessions
2:00 PM - 3:40 PM

Session 11A
2:00 PM Matrix Rounding under the Lp-Discrepancy Measure and Its Application to Digital Halftoning
Tetsuo Asano, Japan Advanced Institute of Science and Technology; Naoki Katoh, Kyoto University, Japan; Koji Obokata, Japan Advanced Institute of Science and Technology; and Takeshi Tokuyama, Tohoku University, Japan
2:25 PM Smoothed Analysis of the Perceptron Algorithm for Linear Programming
Avrim Blum, Carnegie Mellon University; and John Dunagan, Massachusetts Institute of Technology
2:50 PM A Fully Combinatorial Algorithm for Submodular Function Minimization
Satoru Iwata, University of Tokyo, Japan
3:15 PM 0/1 Optimization and 0/1 Primal Separation are Equivalent
Friedrich Eisenbrand, Max-Planck-Institut f?r Informatik, Saarbr?cken, Germany, Giovanni Rinaldi and Paolo Ventura, Istituto di Analisi dei Sistemi ed Informatica, Roma, Italy
Imperial A
Session 11B
2:00 PM Labeling Schemes for Flow and Connectivity
Michal Katz and Nir A. Katz, Bar Ilan University, Israel; Amos Korman and David Peleg, The Weizmann Institute of Science, Israel
2:25 PM Reachability and Distance Queries via 2-hop Labels
Edith Cohen, AT&T Research Laboratories; Eran Halperin, Haim Kaplan and Uri Zwick, Tel Aviv University, Israel
2:50 PM Improved Labeling Scheme for Ancestor Queries
Stephen Alstrup and Theis Rauhe, IT University in Copenhagen, Denmark
3:15 PM A Comparison of Labeling Schemes for Ancestor Queries
Haim Kaplan, Tova Milo and Ronen Shabo, Tel Aviv University, Israel
Imperial B
Session 11C
2:00 PM Incentive-Compatible Online Auctions for Digital Goods
Ziv Bar-Yossef, Kirsten Hildrum and Felix Wu, University of California at Berkeley
2:25 PM Online Algorithms for Market Clearing
Avrim Blum, Tuomas Sandholm and Martin Zinkevich, Carnegie Mellon University
2:50 PM Pricing Multicasting in More Practical Network Models
Micah Adler, University of Massachusetts and Dan Rubenstein, Columbia University
3:15 PM Frugal Path Mechanisms
Aaron Archer and Éva Tardos, Cornell University
Spring B/C
3:40 PM Conference Adjourns  

© 2001 Society for Industrial & Applied Mathematics
Designed by Donaghy's Web Consulting
Last Updated 11/15/01