Sunday, January 9
Session 1A
9:00 AM-10:40 AM
Room: Gold Rush A
- 9:00 e-Approximate Linear Programs: New Bounds and Computation
- Daniel Bienstock, Columbia University
- 9:25 Orthogonal Graph Drawing with Constraints
- Markus Eiglsperger, Universität Tübingen, Germany; Ulrich Fößmeier, Tom Sawyer Software; and Michael Kaufmann, Universität Tübingen, Germany
- 9:50 Fast Practical Solution of Sorting by Reversals
- Alberto Caprara, Università di Bologna, Italy; Giuseppe Lancia, Università di Padova, Italy; and See Kiong Ng, Smithkline Beecham Pharmaceuticals R&D, United Kingdom
- 10:15 Commuting with Delay Prone Buses
- Mayur Datar, Stanford University; and Abhiram Ranade, Indian Institute of Technology-Bombay, India
Session 1B
9:00 AM-10:40 AM
Room: Oregon/Nevada
- 9:00 Coloring Non-uniform Hypergraphs: A New Algorithmic Approach to the General Lovász Local Lemma
- Artur Czumaj and Christian Scheideler, Paderborn University, Germany
- 9:25 On the Complexity of Bicoloring Clique Hypergraphs of Graphs
- J. Kratochvil, Charles University, Czech Republic; and Zs. Tuza, Hungarian Academy of Sciences, Hungary
- 9:50 Weakly Chordal Graph Algorithms via Handles
- Ryan Hayward, University of Alberta, Canada; Jeremy Spinrad, Vanderbilt University; and R. Sritharan, Indiana State University
- 10:15 Recognizing Dart-Free Perfect Graphs
- V. Chvátal, Rutgers University; J. Fonlupt, Université Pierre et Marie Curie, France; L. Sun and A. Zemirline, Université de Bretagne Occidentale, France
Session 1C
9:00 AM-10:40 AM
Room: Gold Rush B
- 9:00 An Optimal Algorithm for Hyperplane Depth in the Plane
- Stefan Langerman and William Steiger, Rutgers University
- 9:25 On Heilbronn's Problem in Higher Dimension
- Hanno Lefmann, Universität Dortmund, Germany
- 9:50 Finding Minimal Triangulations of Convex 3-Polytopes is NP-Hard
- Alexander Below, ETH-Zurich, Switzerland; Jesús A. De Loera, University of California, Davis; and Jürgen Richter-Gebert, ETH-Zurich, Switzerland
- 10:15 A Point-Placement Strategy for Conforming Delaunay Tetrahedralization
- Michael Murphy, University of Maryland, College Park and Los Alamos National Laboratory; David M. Mount, University of Maryland, College Park; and Carl W. Gable, Los Alamos National Laboratory
Session 2: Invited Presentation
Digraph Minors and Algorithms
11:00 AM-12:00 PM
Room: Gold Rush A
The Graph Minors project, originated by Robertson and Seymour, was very successful. It resulted in many theoretical advances (e.g. a proof of Wagner's conjecture), but it also has algorithmic applications, and some of the methods have been successfully used in practical computation.
It now appears possible to extend part of the project to directed graphs. The speaker will review the basics of the Graph Minors theory, and then will discuss generalizations to directed graphs, algorithmic consequences, and open problems.
Robin Thomas
Georgia Institute of Technology
Session 3A
1:30 PM-3:35 PM
Room: Gold Rush A
- 1:30 Cooperative Facility Location Games
- Michel X. Goemans, Massachusetts Institute of Technology; and Martin Skutella, Technische Universität Berlin, Germany
- 1:55 K-Medians, Facility Location, and the Chernoff-Wald Bound
- Neal E. Young, Dartmouth College
- 2:20 Improved Approximation Algorithms for MAX SAT
- Takao Asano, Chuo University, Japan; and David P. Williamson, IBM T. J. Watson Research Center
- 2:45 Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems
- Robert D. Carr, Sandia National Laboratories, Albuquerque; Lisa K. Fleischer, Columbia University; Vitus J. Leung, and Cynthia A. Phillips, Sandia National Laboratories, Albuquerque
- 3:10 Towards a 4/3 Approximation for the Asymmetric Traveling Salesman Problem
- Robert D. Carr, Sandia National Laboratories, Albuquerque; and Santosh Vempala, Massachusetts Institute of Technology
Session 3B
1:30 PM-3:35 PM
Room: Oregon/Nevada
- 1:30 Typical Random 3-SAT Formulae and the Satisfiability Threshold
- Olivier Dubois, CNRS-Université Paris 6, France; Yacine Boufkhad, Université d' Artois, France; and Jacques Mandler, CNRS-Université Paris 6, France
- 1:55 A Lower Bound for DLL Algorithms for k-SAT
- Pavel Pudlak and Russell Impagliazzo, University of California, San Diego
- 2:20 On Permutations with Limited Independence
- Toshiya Itoh and Yoshinori Takei, Tokyo Institute of Technology, Japan; and Jun Tarui, University of Electro-Communications, Japan
- 2:45 Min-Wise versus Linear Independence
- Andrei Z. Broder, Compaq Systems Research Center; and Uriel Feige, Weizmann Institute, Israel
- 3:10 Hamiltonicity and Colorings of Arrangement Graphs
- Stefan Felsner, Freie Universität Berlin, Germany; Ferran Hurtado and Marc Noy, Universitat Politecnica de Catalunya, Spain; and Ileana Streinu, Smith College
Session 3C
1:30 PM-3:35 PM
Room: Gold Rush B
- 1:30 Testing and Spot-Checking of Data Streams
- J. Feigenbaum, AT&T Labs - Research; S. Kannan, University of Pennsylvania; M. Strauss, AT&T Labs - Research; and M. Viswanathan, University of Pennsylvania
- 1:55 Engineering the Compression of Massive Tables: An Experimental Approach
- Adam L. Buchsbaum, Kenneth W. Church, Donald F. Caldwell, Glenn S. Fowler, and S. Muthukrishnan, AT&T Labs - Research
- 2:20 On the Temporal HZY Compression Scheme
- Z. Cohen, Technion - Israel Institute of Technology, Israel; Y. Matias, Tel-Aviv University, Israel; S. Muthukrishnan, AT&T Labs - Research; S. C. Sahinalp, University of Warwick, United Kingdom; J. Ziv, Technion - Israel Institute of Technology, Israel
- 2:45 Height in a Digital Search Tree and the Longest Phrase of the Lempel-Ziv Scheme
- Charles Knessl, University of Illinois, Chicago; and Wojciech Szpankowski, Purdue University, West Lafayette
- 3:10 Communication Complexity of Document Exchange
- Graham Cormode, Mike Paterson and Süleyman Cenk Sahinalp, University of Warwick, United Kingdom; and Uzi Vishkin, University of Maryland, College Park
Session 4A
4:00 PM-6:05 PM
Room: Gold Rush A
- 4:00 Scheduling a Pipelined Operator Graph
- Petra Schuurman, Eindhoven University of Technology, The Netherlands; and Gerhard J. Woeginger, Technical University of Graz, Austria
- 4:25 A PTAS for the Multiple Knapsack Problem
- Chandra Chekuri and Sanjeev Khanna, Bell Laboratories
- 4:50 Approximation Algorithms for Data Placement on Parallel Disks
- Leana Golubchik, University of Maryland, College Park; Sanjeev Khanna, Bell Laboratories; Samir Khuller, University of Maryland, College Park; Ramakrishna Thurimella, University of Denver and University of Maryland, College Park; and An Zhu, University of Maryland, College Park
- 5:15 Movement Minimization in Conveyor Flow Shop Processing
- W. Espelage and E. Wanke, University of Düsseldorf, Germany
- 5:40 Forcing Relations for AND/OR Precedence Constraints
- Rolf H. Möhring, Martin Skutella, and Frederik Stork, Technische Universität Berlin, Germany
Session 4B
4:00 PM-6:05 PM
Room: Oregon/Nevada
- 4:00 The Interlace Polynomial: A New Graph Polynomial
- Richard Arratia, University of Southern California; Béla Bollobás, University of Memphis; and Gregory B. Sorkin, IBM T. J. Watson Research Center
- 4:25 The Complexity of Counting Graph Homomorphisms
- Martin Dyer and Catherine Greenhill, University of Leeds, United Kingdom
- 4:50 A Fast Algorithm to Generate Unlabeled Necklaces
- Frank Ruskey and Joe Sawada, University of Victoria, Canada
- 5:15 Construction of Visual Secret Sharing Schemes with Almost Optimal Contrast
- Christian Kuhlmann and Hans Ulrich Simon, Ruhr-Universität Bochum, Germany
- 5:40 Sharing One Secret vs. Sharing Many Secrets: Tight Bounds on the Average Improvement Ratio
- Giovanni Di Crescenzo, Telcordia Technologies, Inc., and University of California, San Diego
Session 4C
4:00 PM-6:05 PM
Room: Gold Rush B
- 4:00 Algorithmic Strategies in Combinatorial Chemistry
- Deborah Goldman, University of California, Berkeley; Sorin Istrail, Sandia National Laboratories, Albuquerque; Giuseppe Lancia, Università degli Studi di Padova, Italy; Antonio Piccolboni, University of California, Davis; and Brian Walenz, Sandia National Laboratories, Albuquerque
- 4:25 Computing the Quartet Distance Between Evolutionary Trees
- David Bryant, University of Montreal, Canada; John Tsang, Paul Kearney, and Ming Li, University of Waterloo, Canada
- 4:50 A Practical Algorithm for Recovering the Best Supported Edges of an Evolutionary Tree
- David Bryant, University of Montreal, Canada; Vincent Berry, Université de Montpellier II, France; Paul Kearney and Ming Li, University of Waterloo, Canada; Tao Jiang and Todd Wareham, McMaster University, Canada; and Haoyong Zhang, University of Waterloo, Canada
- 5:15 Pattern Discovery on Character Sets and Real-valued Data: Linear Bound on Irredundant Motifs and an Efficient Polynomial Time Algorithm
- Laxmi Parida, Yuan Gao, Dan Platt, Aris Floratos, and Isidore Rigoutsos, IBM T. J. Watson Research Center
- 5:40 Improved Bounds on the Sample Complexity of Learning
- Yi Li and Philip M. Long, National University of Singapore, Singapore; and Aravind Srinivasan, Bell Laboratories, Lucent Technologies
Monday, January 10
Session 5A
9:00 AM-10:40 PM
Room: Gold Rush A
- 9:00 On Local Search and Placement of Meters in Networks
- Samir Khuller, University of Maryland, College Park; Randeep Bhatia, Bell Laboratories; and Robert Pless, University of Maryland, College Park
- 9:25 Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Eran Halperin, Tel-Aviv University, Israel
- 9:50 An Approximation Algorithm for the Covering Steiner Problem
- Goran Konjevod, Carnegie Mellon University and Los Alamos National Laboratory; and R. Ravi, Carnegie Mellon University
- 10:15 On the Red-Blue Set Cover Problem
- Robert D. Carr, Sandia National Laboratories, Albuquerque; Srinivas Doddi, Los Alamos National Laboratory; Goran Konjevod, Carnegie Mellon University and Los Alamos National Laboratory; and Madhav Marathe, Los Alamos National Laboratory
Session 5B
9:00 AM-10:40 PM
Room: Oregon/Nevada
- 9:00 Approximate Congruence in Nearly Linear Time
- Piotr Indyk and Suresh Venkatasubramanian, Stanford University
- 9:25 Locally Lifting the Curse of Dimensionality for Nearest Neighbor Search
- Peter N. Yianilos, NEC Research Institute and Princeton University
- 9:50 Dimensionality Reduction Techniques for Proximity Problems
- Piotr Indyk, Stanford University
- 10:15 Expected-Case Complexity of Approximate Nearest Neighbor Searching
- Sunil Arya and Ho-Yam Addy Fu, The Hong Kong University of Science and Technology, China
Session 5C
9:00 AM-10:40 PM
Room: Gold Rush B
- 9:00 A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry
- Ting Chen, Harvard Medical School; Ming-Yang Kao, Yale University; Matthew Tepel, John Rush, and George M. Church, Harvard Medical School
- 9:25 Algorithms for Optimizing Production DNA Sequencing
- Eva Czabarka, University of South Carolina, Columbia; Goran Konjevod, Carnegie Mellon University and Los Alamos National Laboratory; Madhav V. Marathe, Allon G. Percus, and David C. Torney, Los Alamos National Laboratory
- 9:50 Estimating DNA Sequence Entropy
- J. Kevin Lanctot, Ming Li, and En-hui Yang, University of Waterloo, Canada
- 10:15 Selective Mapping: A Discrete Optimization Approach to Selecting a Population Subset for Use in a High-Density Genetic Mapping Project
- Daniel G. Brown, Todd J. Vision, and Steven D. Tanksley, Cornell University
Session 6: Invited Presentation
Cutting Planes and the Traveling Salesman Problem
11:00 AM-12:00 PM
Room: Gold Rush A
TSPLIB is Gerhard Reinelt's library of some hundred instances of the traveling salesman problem. Some of these instances arise from the task of drilling holes in printed circuit boards; others arise in X-ray crystallography; yet others have been constructed artificially. None of them (with a single exception) is contrived to be hard and none of them is contrived to be easy; their sizes range from 17 to 85,900 cities; some of them have been solved and others
have not.
Following the theoretical studies of J.B. Robinson and H.W. Kuhn in the late 1940s and the early 1950s, G.B. Dantzig, R. Fulkerson, and S.M. Johnson demonstrated in 1954 that large instances of the TSP could be solved by linear programming. Their approach remains the only known tool for solving nontrivial TSP instances with more than several hundred cities; over the years, it has evolved further through the work of M.Grötschel, S. Hong, M. Jünger, P. Miliotis, D. Naddef, M. Padberg, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and others.
We enumerate some of its refinements that allowed us to solve more than twenty previously unsolved instances from the TSPLIB. One of these is the instance with 225 cities, ts225, that was contrived to be hard; the sizes of the others range from 1,000 to 13,509 cities.
This is joint work with D. Applegate, R. Bixby, and W. Cook.
V. Chvátal
Rutgers University
Session 7A
1:30 PM-3:35 PM
Room: Gold Rush A
- 1:30 Caching in Networks
- Friedhelm Meyer auf der Heide, University of Paderborn, Germany; Berthold Vöcking, International Computer Science Institute; and Matthias Westermann, University of Paderborn, Germany
- 1:55 Instability of FIFO in Session-Oriented Networks
- Matthew Andrews, Bell Laboratories
- 2:20 The Effects of Temporary Sessions on Network Performance
- Matthew Andrews and Lisa Zhang, Bell Laboratories
- 2:45 Randomized Greedy Hot-Potato Routing
- Costas Busch, Maurice Herlihy, and Roger Wattenhofer, Brown University
- 3:10 On Deciding Stability of Some Scheduling Policies in Queueing Systems
- David Gamarnik, IBM T. J. Watson Research Center
Session 7B
1:30 PM-3:35 PM
Room: Oregon/Nevada
- 1:30 Restructuring Ordered Binary Trees
- William Evans, University of Arizona; and David Kirkpatrick, University of British Columbia, Canada
- 1:55 Faster Deterministic Dictionaries
- Rasmus Pagh, BRICS, University of Aarhus, Denmark
- 2:20 Competitive Tree-Structured Dictionaries
- Michael T. Goodrich, Johns Hopkins University
- 2:45 Even Strongly Universal Hashing is Pretty Fast
- Mikkel Thorup, AT&T Labs - Research
- 3:10 Word Encoding Tree Connectivity Works
- Stephen Alstrup, The IT University in Copenhagen, Denmark; Jens Peter Secher, University of Copenhagen, Denmark; and Mikkel Thorup, AT&T Labs - Research
Session 7C
1:30 PM-3:35 PM
Room: Gold Rush B
- 1:30 Algorithms for Minimum Volume Enclosing Simplex in R3
- Yunhong Zhou and Subhash Suri, Washington University
- 1:55 Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells
- Pankaj K. Agarwal, Duke University; Boris Aronov, Polytechnic University; and Micha Sharir, Tel Aviv University, Israel and Courant Institute of Mathematical Sciences, New York University
- 2:20 Evaluating the Cylindricity of a Nominally Cylindrical Point Set
- Olivier Devillers, INRIA, France; and Franco P. Preparata, Brown University
- 2:45 Approximation Algorithms for Layered Manufacturing
- Pankaj K. Agarwal and Pavan K. Desikan, Duke University
- 3:10 Approximation Algorithms for Projective Clustering
- Pankaj K. Agarwal and Cecilia M. Procopiuc, Duke University
Session 8A
4:00 PM-6:05 PM
Room: Gold Rush A
- 4:00 Scheduling to Minimize Average Stretch without Migration
- Luca Becchetti and Stefano Leonardi, Università di Roma "La Sapienza", Italy; and S. Muthukrishnan, AT&T Labs - Research
- 4:25 Minimizing Maximum Response Time in Scheduling Broadcasts
- Yair Bartal, Bell Laboratories, Lucent Technologies; and S. Muthukrishnan, AT&T Labs - Research
- 4:50 Applying Extra-Resource Analysis to Load Balancing
- Mark Brehob, Eric Torng, and Patchrawat Uthaisombut, Michigan State University
- 5:15 Balancing Steiner Trees and Shortest Path Trees Online
- Ashish Goel and Kamesh Munagala, Stanford University
- 5:40 Generating Adversaries for Request-Answer Games
- Todd Gormley, Michigan State University; Nicholas Reingold, AT&T Labs - Research; Eric Torng, Michigan State University; and Jeffery R. Westbrook, AT&T Labs - Research
Session 8B
4:00 PM-6:05 PM
Room: Oregon/Nevada
- 4:00 Maintaining Hierarchical Graph Views
- Adam L. Buchsbaum and Jeffery R. Westbrook, AT&T Labs - Research
- 4:25 Improved Classification via Connectivity Information
- Andrei Z. Broder, Compaq Systems Research Center; Robert Krauthgamer, Weizmann Institute of Science, Israel; and Michael Mitzenmacher, Harvard University
- 4:50 Efficient Dynamic Traitor Tracing
- Omer Berkman and Michal Parnas, The Academy College of Tel-Aviv-Yaffo, Israel; and Jiri Sgall, Mathematical Institute and Charles University, Czech Republic
- 5:15 Watermarking Maps: Hiding Information in Structured Data
- Sanjeev Khanna and Francis Zane, Bell Laboratories
- 5:40 Strictly Non-blocking WDM Cross-connects
- April Rasala, Massachusetts Institute of Technology; and Gordon Wilfong, Bell Laboratories, Lucent Technologies
Session 8C
4:00 PM-6:05 PM
Room: Gold Rush B
- 4:00 An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings
- Martin Dyer, University of Leeds, United Kingdom; Leslie Ann Goldberg, University of Warwick, United Kingdom; Catherine Greenhill, University of Leeds, United Kingdom; Mark Jerrum, University of Edinburgh, United Kingdom; and Michael Mitzenmacher, Harvard University
- 4:25 A Faster Method for Sampling Independent Sets
- Mark Huber, Cornell University
- 4:50 Strong Bias of Group Generators: An Obstacle to the "Product Replacement Algorithm"
- László Babai, University of Chicago; and Igor Pak, Yale University
- 5:15 Random Three-Dimensional Tilings of Aztec Octahedra and Tetrahedra: An Extension of Domino Tilings
- Dana Randall and Gary Yngve, Georgia Institute of Technology
- 5:40 An Algebraic Method to Compute a Shortest Path of Local Flips Between Two Tilings
- Eric Rémila, LIP, ENS-Lyon, CNRS, France and Université Jean Monnet Saint-Etienne, France
Tuesday, January 11
Session 9A
9:00 AM-10:40 AM
Room: Gold Rush A
- 9:00 Coloring Powers of Planar Graphs
- Geir Agnarsson and Magnús M. Halldórsson, University of Iceland, Iceland
- 9:25 Directed Network Design with Orientation Constraints
- Sanjeev Khanna, Joseph (Seffi) Naor, and F. Bruce Shepherd, Bell Laboratories, Lucent Technologies
- 9:50 A (2 + e)-Approximation Scheme for Minimum Domination on Circle Graphs
- Mirela Damian-Iordache, University of Iowa; and Sriram V. Pemmaraju, Indian Institute of Technology-Bombay, India
- 10:15 An Approximation Algorithm for Finding a Long Path in Hamiltonian Graphs
- Sundar Vishwanathan, Indian Institute of Technology-Bombay, India
Session 9B
9:00 AM-10:40 AM
Room: Oregon/Nevada
- 9:00 TSP-Based Curve Reconstruction in Polynomial Time
- Ernst Althaus and Kurt Mehlhorn, Max-Planck-Institut für Informatik, Germany
- 9:25 A Tree-Edit-Distance Algorithm for Comparing Simple, Closed Shapes
- Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, and Ben Kimia, Brown University
- 9:50 Computing the Arrangement of Curve Segments: Divide-and-Conquer Algorithms via Sampling
- Nancy M. Amato, Texas A&M University; Michael T. Goodrich, Johns Hopkins University; and Edgar A. Ramos, Max-Planck-Institut für Informatik, Germany
- 10:15 Optimizing the Sum of Linear Fractional Functions and Applications
- Danny Z. Chen and Ovidiu Daescu, University of Notre Dame; Yang Dai, Tokyo Institute of Technology, Japan; Naoki Katoh, Kyoto University, Japan; Xiaodong Wu and Jinhui Xu, University of Notre Dame
Session 9C
9:00 AM-10:40 AM
Room: Gold Rush B
- 9:00 Edge-Disjoint Paths in Expander Graphs
- Alan M. Frieze, Carnegie Mellon University
- 9:25 Escaping a Grid by Edge-Disjoint Paths
- Wun-Tat Chan, Francis Y.L. Chin, and Hing-Fung Ting, University of Hong Kong, China
- 9:50 Fast Randomized Algorithms for Computing Minimum {3,4,5,6}-Way Cuts
- Matthew S. Levine, Massachusetts Institute of Technology
- 10:15 Adaptive Set Intersections, Unions, and Differences
- Erik D. Demaine, University of Waterloo, Canada; Alejandro Lopez-Ortiz, University of New Brunswick, Canada; and J. Ian Munro, University of Waterloo, Canada
Session 10: Invited Presentation
The Whole Genome Assembly of Drosophila
11:00 AM-12:00 PM
Room: Gold Rush A
We report on the design of a whole genome shotgun assembler and its application to the sequencing of the Drosophila genome. Celera's whole genome strategy consists of randomly sampling pairs of sequence reads of length 500-600 that are at approximately known distances from each other - short pairs at a distance of 2K, long pairs at 10K, and BAC-end pairs at 150K. For Drosophila, we collected 1.6 million pairs whereby the sum of the lengths of the reads is roughly 12 times the length of the genome (~130 million), a so called 12X shotgun data set. The reads were further collected so there are two short read pairs to every long read pair, with a sprinkling of roughly 12,000 BAC-end pairs. The experimental accuracy of the read sequences is roughly 98%. Given this data set, the problem is to determine the sequence of Drosophila's 4 chromosomes that are estimated to be 10-15% repetitive sequence.
The assembler computes all overlaps between the reads in under 13 hours on a 4-processor Compaq platform, and completes the entire assembly process in under 36 hours. We layer the ideas of uncontested interval graph collapsing, confirmed read pairs, and mutually confirming paths to yield a strategy that makes remarkably few errors. The assembler correctly identifies all unique stretches of the genome, correctly building contigs for each and ordering them into scaffolds spanning each of the chromosomes. Thus all useful proteomic information has been assembled as of this writing. We will be reporting on the extent to which the ubiquitous repeats that lie between these contigs are resolved. Preliminary trials suggest 99.97% or more of the genome will be assembled, far exceeding the 95% standard set for human chromosome 22. The design of the assembler provides a complete audit trail of the moves it makes in assembling a data set and is capable of incorporating external data such as independently sequenced segments of the given genome, lightly shotgunned (3-5X) segments, and smaller marker sequences located on the genome (STSs). By arranging assembly to be concurrent with data collection, this assembler should achieve a comparable result on the human genome with a 3 month computation on a 10-processor platform.
Gene Myers
Celera Genomics
Session 11A
1:45 PM-3:50 PM
Room: Gold Rush A
- 1:45 A 2 + e Approximation Algorithm for the k-MST Problem
- Sanjeev Arora and George Karakostas, Princeton University
- 2:10 The Prize Collecting Steiner Tree Problem: Theory and Practice
- David S. Johnson, AT&T Labs - Research; Maria Minkoff, Massachusetts Institute of Technology; and Steven Phillips, AT&T Labs - Research
- 2:35 Improved Steiner Tree Approximation in Graphs
- Gabriel Robins, University of Virginia; and Alexander Zelikovsky, Georgia State University
- 3:00 The Rectilinear Steiner Arborescence Problem is NP-Complete
- Weiping Shi and Chen Su, University of North Texas
- 3:25 Improved Bandwidth Approximation for Trees
- Anupam Gupta, University of California, Berkeley
Session 11B
1:45 PM-3:50 PM
Room: Oregon/Nevada
- 1:45 Faster Algorithms for String Matching with k Mismatches
- Amihood Amir, Bar-Ilan University, Israel and Georgia Institute of Technology; Moshe Lewenstein, Bar-Ilan University, Israel; and Ely Porat, Bar-Ilan University, Israel and Weizmann Institute, Israel
- 2:10 On the Shared Substring Alignment Problem
- Gad M. Landau, Polytechnic University and Haifa University, Israel; and Michal Ziv-Ukelson, Haifa University, Israel
- 2:35 Real Scaled Matching
- Amihood Amir, Bar-Ilan University, Israel and Georgia Institute of Technology; Ayelet Butman and Moshe Lewenstein, Bar-Ilan University, Israel
- 3:00 Inplace Run-Length 2d Compressed Search
- Amihood Amir, Bar-Ilan University, Israel; Gad M. Landau, Haifa University, Israel; Dina Sokol, Bar-Ilan University, Israel
- 3:25 Pattern Matching in Dynamic Texts
- Stephen Alstrup, The University in Copenhagen, Denmark; Gerth Stølting Brodal and Theis Rauhe, University of Aarhus, Denmark
Session 11C
1:45 PM-3:50 PM
Room: Gold Rush B
- 1:45 Towards A Theory of Cache-Efficient Algorithms
- Sandeep Sen, University of North Carolina, Chapel Hill and Indian Institute of Technology-New Delhi, India; and Siddhartha Chatterjee, University of North Carolina, Chapel Hil
l
- 2:10 Efficient Bundle Sorting
- Yossi Matias and Eran Segal, Tel-Aviv University, Israel; and Jeffrey Scott Vitter, Duke University
- 2:35 Fast Concurrent Access to Parallel Disks
- Peter Sanders, Max-Planck-Institute for Computer Science, Germany; Sebastian Egner and Jan Korst, Philips Research Laboratories, The Netherlands
- 3:00 On External Memory Graph Traversal
- Adam L. Buchsbaum, AT&T Labs - Research; Michael Goldwasser, Princeton University; Suresh Venkatasubramanian, Stanford University; and Jeffery R. Westbrook, AT&T Labs - Research
- 3:25 Deterministic Broadcasting in Unknown Radio Networks
- Bogdan S. Chlebus, Uniwersytet Warszawski, Poland; Leszek Gasieniec and Alan Gibbons, The University of Liverpool, United Kingdom; Andrzej Pelc, Université du Québec à Hull, Canada; and Wojciech Rytter, Uniwersytet Warszawski, Poland and The University of Liverpool, United Kingdom
Session 12A
4:15 PM-5:55 PM
Room: Gold Rush A
- 4:15 New and Improved Algorithms for Minsum Shop Scheduling
- Maurice Queyranne, University of British Columbia, Canada; and Maxim Sviridenko, Sobolev Institute of Mathematics, Russia
- 4:40 Off-Line Admission Control for General Scheduling Problems
- Cynthia A. Phillips, Sandia National Labortories, Albuquerque; R. N. Uma and Joel Wein, Polytechnic University
- 5:05 Approximating the Maximum Quadratic Assignment Problem
- Esther M. Arkin, State University of New York, Stony Brook; and Refael Hassin, Tel-Aviv University, Israel
- 5:30 Accurate Approximations for Asian Options
- Donald Aingworth, Rajeev Motwani, and Jeffrey D. Oldham, Stanford University
Session 12B
4:15 PM-5:55 PM
Room: Oregon/Nevada
- 4:15 Finite-Resolution Hidden Surface Removal
- Jeff Erickson, University of Illinois, Urbana-Champaign
- 4:40 On Incremental Rendering of Silhouette Maps of Polyhedral Scene
- Li Zhang, Alon Efrat, Leonidas J. Guibas, Olaf A. Hall-Holt, Stanford University
- 5:05 Computing Contour Trees in All Dimensions
- Hamish Carr, University of British Columbia, Canada; Jack Snoeyink, University of British Columbia, Canada and University of North Carolina, Chapel Hill; and Ulrike Axen, Washington State University
- 5:30 Sweeping Simple Polygons with a Chain of Guards
- Alon Efrat and Leonidas J. Guibas, Stanford University; Sariel Har-Peled, Tel Aviv University, Israel; David C. Lin, Stanford University; Joseph S. B. Mitchell, State University of New York, Stony Brook; T. M. Murali, Stanford University
Session 12C
4:15 PM-5:55 PM
Room: Gold Rush B
- 4:15 Finding the Closest Lattice Vector When It's Unusually Close
- Philip N. Klein, Brown University
- 4:40 A New Bound for the Carathéodory Rank of the Bases of a Matroid
- J. C. de Pina and J. Soares, Universidade de São Paolo, Brazil
- 5:05 Minimum Ratio Canceling is Oracle Polynomial for Linear Programming, but Not Strongly Polynomial, Even for Networks
- S. Thomas McCormick, University of British Columbia, Canada; and Akiyoshi Shioura, Sophia University, Japan
- 5:30 Nearly Optimal Computations with Structured Matrices
- Victor Y. Pan, Lehman College, City University of New York
Created 11/7/99; Last Updated 11/7/99