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


© 1999, Society for Industrial and Applied Mathematics
Designed by Donaghy's Web Consulting
Created 11/7/99; Last Updated 11/7/99