Day/Time
|
Session
|
Room
|
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
IP1
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
IP2
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 |
Registration
|
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 |
|