14. SODA 2003: Baltimore, Maryland, USA

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA. ISBN 0-89871-538-5, ACM/SIAM, 2003

Session 1A

Yijie Han:
Optimal parallel selection. 1-9
Electronic Edition (ACM DL) BibTeX
Sampath Kannan, Sanjeev Khanna:
Selection with monotone comparison cost. 10-17
Electronic Edition (ACM DL) BibTeX
Robert Krauthgamer, Ori Sasson:
Property testing of data dimensionality. 18-27
Electronic Edition (ACM DL) BibTeX
Ronald Fagin, Ravi Kumar, D. Sivakumar:
Comparing top k lists. 28-36
Electronic Edition (ACM DL) BibTeX

Session 1B

Sandy Irani, Sandeep K. Shukla, Rajesh K. Gupta:
Algorithms for power savings. 37-46
Electronic Edition (ACM DL) BibTeX
Susanne Albers, Helge Bals:
Dynamic TCP acknowledgement: penalizing long delays. 47-55
Electronic Edition (ACM DL) BibTeX
Lisa Fleischer, Jay Sethuraman:
Approximately optimal control of fluid networks. 56-65
Electronic Edition (ACM DL) BibTeX
Lisa Fleischer, Martin Skutella:
Minimum cost flows over time without intermediate storage. 66-75
Electronic Edition (ACM DL) BibTeX

Session 1C

Michael Elkin, Guy Kortsarz:
Sublogarithmic approximation for telephone multicast: path out of jungle. 76-85
Electronic Edition (ACM DL) BibTeX
Andreas S. Schulz, Nicolás E. Stier Moses:
On the performance of user equilibria in traffic networks. 86-87
Electronic Edition (ACM DL) BibTeX
Aaron Archer, David P. Williamson:
Faster approximation algorithms for the minimum latency problem. 88-96
Electronic Edition (ACM DL) BibTeX
Yoo Ah Kim:
Data migration to minimize the average completion time. 97-98
Electronic Edition (ACM DL) BibTeX

Session 2: invited plenary abstract

Ian H. Witten:
Browsing around a digital library. 99-99
Electronic Edition (ACM DL) BibTeX

Session 3A

John Hershberger, Subhash Suri:
Binary space partitions for 3D subdivisions. 100-108
Electronic Edition (ACM DL) BibTeX
Bettina Speckmann, Csaba D. Tóth:
Allocating vertex pi-guards in simple polygons via pseudo-triangulations. 109-118
Electronic Edition (ACM DL) BibTeX
Gill Barequet, Michael T. Goodrich, Aya Levi-Steiner, Dvir Steiner:
Straight-skeleton based contour interpolation. 119-127
Electronic Edition (ACM DL) BibTeX
Marshall W. Bern, David Eppstein:
Möbius-invariant natural neighbor interpolation. 128-129
Electronic Edition (ACM DL) BibTeX

Session 3B

George S. Lueker:
Improved bounds on the average length of longest common subsequences. 130-131
Electronic Edition (ACM DL) BibTeX
Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Oliver Riordan:
Directed scale-free graphs. 132-139
Electronic Edition (ACM DL) BibTeX
Colin Cooper, Alan M. Frieze:
The cover time of sparse random graphs. 140-147
Electronic Edition (ACM DL) BibTeX
Alan M. Frieze, Boris Pittel:
Perfect matchings in random graphs with prescribed minimal degree. 148-157
Electronic Edition (ACM DL) BibTeX

Session 3C

Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, Jeremy Spinrad:
Certifying algorithms for recognizing interval graphs and permutation graphs. 158-167
Electronic Edition (ACM DL) BibTeX
Fedor V. Fomin, Dimitrios M. Thilikos:
Dominating sets in planar graphs: branch-width and exponential speed-up. 168-177
Electronic Edition (ACM DL) BibTeX
Mikkel Thorup:
Quick and good facility location. 178-185
Electronic Edition (ACM DL) BibTeX
Sean Curran, Orlando Lee, Xingxing Yu:
Chain decompositions and independent trees in 4-connected graphs. 186-191
Electronic Edition (ACM DL) BibTeX

Session 4A

Piotr Berman, Piotr Krysta:
Optimizing misdirection. 192-201
Electronic Edition (ACM DL) BibTeX
Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu:
Online learning in online auctions. 202-204
Electronic Edition (ACM DL) BibTeX
Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos:
An approximate truthful mechanism for combinatorial auctions with single parameter agents. 205-214
Electronic Edition (ACM DL) BibTeX
Andrew V. Goldberg, Jason D. Hartline:
Competitiveness via consensus. 215-222
Electronic Edition (ACM DL) BibTeX

Session 4B

Petros Drineas, Ravi Kannan:
Pass efficient algorithms for approximating large matrices. 223-232
Electronic Edition (ACM DL) BibTeX
S. Muthukrishnan, Martin Strauss:
Rangesum histograms. 233-242
Electronic Edition (ACM DL) BibTeX
Anna C. Gilbert, S. Muthukrishnan, Martin Strauss:
Approximation of functions over redundant dictionaries using coherence. 243-252
Electronic Edition (ACM DL) BibTeX
Anupam Gupta, Francis Zane:
Counting inversions in lists. 253-254
Electronic Edition (ACM DL) BibTeX

Session 4C

Marcel Dhiflaoui, Stefan Funke, Carsten Kwappik, Kurt Mehlhorn, Michael Seel, Elmar Schömer, Ralph Schulte, Dennis Weber:
Certifying and repairing solutions to large LPs how good are LP-solvers? 255-256
Electronic Edition (ACM DL) BibTeX
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar:
An improved approximation algorithm for the 0-extension problem. 257-265
Electronic Edition (ACM DL) BibTeX
Kamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour:
Packing Steiner trees. 266-274
Electronic Edition (ACM DL) BibTeX
Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang:
Integrality ratio for group Steiner trees and directed steiner trees. 275-284
Electronic Edition (ACM DL) BibTeX

Session 5A

Joachim Giesen, Matthias John:
The flow complex: a data structure for geometric modeling. 285-294
Electronic Edition (ACM DL) BibTeX
Siu-Wing Cheng, Sheung-Hung Poon:
Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio. 295-304
Electronic Edition (ACM DL) BibTeX
Jean-Daniel Boissonnat, Menelaos I. Karavelas:
On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres. 305-312
Electronic Edition (ACM DL) BibTeX
Olivier Devillers, Monique Teillaud:
Perturbations and vertex removal in a 3D delaunay triangulation. 313-319
Electronic Edition (ACM DL) BibTeX
Menelaos I. Karavelas, Ioannis Z. Emiris:
Root comparison techniques applied to computing the additively weighted Voronoi diagram. 320-329
Electronic Edition (ACM DL) BibTeX

Session 5B

Mary Cryan, Martin E. Dyer, Haiko Müller, Leen Stougie:
Random walks on the vertices of transportation polytopes with constant number of sources. 330-339
Electronic Edition (ACM DL) BibTeX
Noga Alon, Michael R. Capalbo:
Smaller explicit superconcentrators. 340-346
Electronic Edition (ACM DL) BibTeX
Mohammad R. Salavatipour:
A (1+epsilon)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma. 347-356
Electronic Edition (ACM DL) BibTeX
Abraham Flaxman:
A spectral technique for random satisfiable 3CNF formulas. 357-363
Electronic Edition (ACM DL) BibTeX
Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin:
Random MAX SAT, random MAX CUT, and their phase transitions. 364-373
Electronic Edition (ACM DL) BibTeX

Session 5C

Guy E. Blelloch, Bruce M. Maggs, Shan Leung Maverick Woo:
Space-efficient finger search on degree-balanced search trees. 374-383
Electronic Edition (ACM DL) BibTeX
James Aspnes, Gauri Shah:
Skip graphs. 384-393
Electronic Edition (ACM DL) BibTeX
Surender Baswana, Ramesh Hariharan, Sandeep Sen:
Maintaining all-pairs approximate shortest paths under deletion of edges. 394-403
Electronic Edition (ACM DL) BibTeX
Liam Roditty:
A faster and simpler fully dynamic transitive closure. 404-412
Electronic Edition (ACM DL) BibTeX

Session 6: invited plenary abstract

S. Muthukrishnan:
Data streams: algorithms and applications. 413-413
Electronic Edition (ACM DL) BibTeX

Session 7A

Béla Bollobás, Don Coppersmith, Michael Elkin:
Sparse distance preservers and additive spanners. 414-423
Electronic Edition (ACM DL) BibTeX
Yair Bartal, Manor Mendel:
Multi-embedding and path approximation of metric spaces. 424-433
Electronic Edition (ACM DL) BibTeX
Mihai Badoiu:
Approximation algorithm for embedding metrics into a two-dimensional space. 434-443
Electronic Edition (ACM DL) BibTeX
Valerie King, Li Zhang, Yunhong Zhou:
On the complexity of distance-based evolutionary tree reconstruction. 444-453
Electronic Edition (ACM DL) BibTeX

Session 7B

Anupam Gupta:
Improved results for directed multicut. 454-455
Electronic Edition (ACM DL) BibTeX
Jesper Makholm Byskov:
Algorithms for k-colouring and finding maximal independent sets. 456-457
Electronic Edition (ACM DL) BibTeX
Sriram V. Pemmaraju, Kittikorn Nakprasit, Alexandr V. Kostochka:
Equitable colorings with constant number of colors. 458-459
Electronic Edition (ACM DL) BibTeX
Harold N. Gabow:
Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph. 460-469
Electronic Edition (ACM DL) BibTeX

Session 7C

Ravi Kumar, Alexander Russell:
A note on the set systems used for broadcast encryption. 470-471
Electronic Edition (ACM DL) BibTeX
Chris Peikert, Abhi Shelat, Adam Smith:
Lower bounds for collusion-secure fingerprinting. 472-479
Electronic Edition (ACM DL) BibTeX
Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum property testing. 480-488
Electronic Edition (ACM DL) BibTeX
Wim van Dam, Sean Hallgren, Lawrence Ip:
Quantum algorithms for some hidden shift problems. 489-498
Electronic Edition (ACM DL) BibTeX

Session 8A

Ashish Goel, Deborah Estrin:
Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. 499-505
Electronic Edition (ACM DL) BibTeX
Benjamin Doerr:
Non-independent randomized rounding. 506-507
Electronic Edition (ACM DL) BibTeX
Nikhil Bansal, Kedar Dhamdhere:
Minimizing weighted flow time. 508-516
Electronic Edition (ACM DL) BibTeX
Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Könemann:
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph. 517-522
Electronic Edition (ACM DL) BibTeX

Session 8B

Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova:
Lower bounds for embedding edit distance into normed spaces. 523-526
Electronic Edition (ACM DL) BibTeX
Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair:
Embedding k-outerplanar graphs into l1. 527-536
Electronic Edition (ACM DL) BibTeX
Venkatesan Guruswami, Piotr Indyk:
Embeddings and non-approximability of geometric problems. 537-538
Electronic Edition (ACM DL) BibTeX

Session 8C

Piotr Indyk:
Better algorithms for high-dimensional proximity problems via asymmetric embeddings. 539-545
Electronic Edition (ACM DL) BibTeX
Gerth Stølting Brodal, Rolf Fagerberg:
Lower bounds for external memory dictionaries. 546-554
Electronic Edition (ACM DL) BibTeX
Enoch Peserico:
Online paging with arbitrary associativity. 555-564
Electronic Edition (ACM DL) BibTeX
James D. Fix:
The set-associative cache performance of search trees. 565-572
Electronic Edition (ACM DL) BibTeX
Raffaella Gentilini, Carla Piazza, Alberto Policriti:
Computing strongly connected components in a linear number of symbolic steps. 573-582
Electronic Edition (ACM DL) BibTeX

Session 9A

Uli Wagner:
On the rectilinear crossing number of complete graphs. 583-588
Electronic Edition (ACM DL) BibTeX
Helmut Alt, Alon Efrat, Günter Rote, Carola Wenk:
Matching planar maps. 589-598
Electronic Edition (ACM DL) BibTeX
David Eppstein:
Dynamic generators of topologically embedded graphs. 599-608
Electronic Edition (ACM DL) BibTeX
Sergei Bespamyatnikh:
Computing homotopic shortest paths in the plane. 609-617
Electronic Edition (ACM DL) BibTeX
Christian Worm Mortensen:
Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. 618-627
Electronic Edition (ACM DL) BibTeX

Session 9B

Chandra Chekuri, Sanjeev Khanna:
Edge disjoint paths revisited. 628-637
Electronic Edition (ACM DL) BibTeX
Markus Bläser:
A new approximation algorithm for the asymmetric TSP with triangle inequality. 638-645
Electronic Edition (ACM DL) BibTeX
Moshe Lewenstein, Maxim Sviridenko:
Approximating asymmetric maximum TSP. 646-654
Electronic Edition (ACM DL) BibTeX
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao:
The k-traveling repairman problem. 655-664
Electronic Edition (ACM DL) BibTeX
William Hesse:
Directed graphs requiring large numbers of shortcuts. 665-669
Electronic Edition (ACM DL) BibTeX

Session 9C

Gianni Franceschini, Roberto Grossi:
Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time. 670-678
Electronic Edition (ACM DL) BibTeX
Daniel K. Blandford, Guy E. Blelloch, Ian A. Kash:
Compact representations of separable graphs. 679-688
Electronic Edition (ACM DL) BibTeX
Stephen Alstrup, Philip Bille, Theis Rauhe:
Labeling schemes for small distances in trees. 689-698
Electronic Edition (ACM DL) BibTeX
Mikkel Thorup:
On AC⁰ implementations of fusion trees and atomic heaps. 699-707
Electronic Edition (ACM DL) BibTeX

Session 10: invited plenary abstract

Persi Diaconis:
Who cares about permanents? 708-708
Electronic Edition (ACM DL) BibTeX

Session 11A

Dieter Kratsch, Jeremy Spinrad:
Between O(nm) and O(n alpha). 709-716
Electronic Edition (ACM DL) BibTeX
Devdatt P. Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan:
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. 717-724
Electronic Edition (ACM DL) BibTeX
Raja Jothi, Balaji Raghavachari, Subramanian Varadarajan:
A 5/4-approximation algorithm for minimum 2-edge-connectivity. 725-734
Electronic Edition (ACM DL) BibTeX
Chaitanya Swamy, David B. Shmoys:
Fault-tolerant facility location. 735-736
Electronic Edition (ACM DL) BibTeX

Session 11B

Edith Cohen, Amos Fiat, Haim Kaplan:
Efficient sequences of trials. 737-746
Electronic Edition (ACM DL) BibTeX
Günter Rote:
Pursuit-evasion with imprecise target location. 747-753
Electronic Edition (ACM DL) BibTeX
Venkatesan Guruswami, Igor Shparlinski:
Unconditional proof of tightness of Johnson bound. 754-755
Electronic Edition (ACM DL) BibTeX
Richard J. Lipton, Nisheeth K. Vishnoi:
Deterministic identity testing for multivariate polynomials. 756-760
Electronic Edition (ACM DL) BibTeX

Session 11C

Nir Andelman, Yishay Mansour, An Zhu:
Competitive queueing policies for QoS switches. 761-770
Electronic Edition (ACM DL) BibTeX
William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosén:
Dynamic routing on networks with fixed-size buffers. 771-780
Electronic Edition (ACM DL) BibTeX
Lali Barrière, Pierre Fraigniaud, Lata Narayanan, Jaroslav Opatrny:
Dynamic construction of Bluetooth scatternets of fixed degree and low diameter. 781-790
Electronic Edition (ACM DL) BibTeX
Amotz Bar-Noy, Richard E. Ladner, Tami Tamir:
Scheduling techniques for media-on-demand. 791-80
Electronic Edition (ACM DL) BibTeX

Session 12A

Mihai Badoiu, Kenneth L. Clarkson:
Smaller core-sets for balls. 801-802
Electronic Edition (ACM DL) BibTeX
Leonidas J. Guibas, An Nguyen, Li Zhang:
Zonotopes as bounding volumes. 803-812
Electronic Edition (ACM DL) BibTeX
Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler:
Sublinear-time approximation of Euclidean minimum spanning tree. 813-822
Electronic Edition (ACM DL) BibTeX
Adrian Dumitrescu:
An approximation algorithm for cutting out convex polygons. 823-827
Electronic Edition (ACM DL) BibTeX

Session 12B

S. Muthukrishnan, Torsten Suel, Radek Vingralek:
Inferring tree topologies using flow tests. 828-829
Electronic Edition (ACM DL) BibTeX
Peter Winkler, Lisa Zhang:
Wavelength assignment and generalized interval graph coloring. 830-831
Electronic Edition (ACM DL) BibTeX
Carla P. Gomes, Rommel G. Regis, David B. Shmoys:
An improved approximation algorithm for the partial latin square extension problem. 832-833
Electronic Edition (ACM DL) BibTeX
Hung Q. Ngo, Van H. Vu:
Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs. 834-840
Electronic Edition (ACM DL) BibTeX

Session 12C

Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter:
High-order entropy-compressed text indexes. 841-850
Electronic Edition (ACM DL) BibTeX
Richard Cole, Moshe Lewenstein:
Multidimensional matching and fast search in suffix trees. 851-852
Electronic Edition (ACM DL) BibTeX
Amihood Amir, Gad M. Landau, Dina Sokol:
Inplace 2D matching in compressed images. 853-862
Electronic Edition (ACM DL) BibTeX
Ming Li, Xin Chen, Xin Li, Bin Ma, Paul M. B. Vitányi:
The similarity metric. 863-872
Electronic Edition (ACM DL) BibTeX