14. SODA 2003: Baltimore, Maryland, USA

Session 1A

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

Session 1B

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

Session 1C

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

Session 2: invited plenary abstract

• Ian H. Witten:
  Browsing around a digital library. 99-99
  

Session 3A

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

Session 3B

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

Session 3C

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

Session 4A

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

Session 4B

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

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
  
• Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar:
  An improved approximation algorithm for the 0-extension problem. 257-265
  
• Kamal Jain, Mohammad Mahdian, Mohammad R. Salavatipour:
  Packing Steiner trees. 266-274
  
• Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, Nan Wang:
  Integrality ratio for group Steiner trees and directed steiner trees. 275-284
  

Session 5A

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

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
  
• Noga Alon, Michael R. Capalbo:
  Smaller explicit superconcentrators. 340-346
  
• Mohammad R. Salavatipour:
  A (1+epsilon)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász Local Lemma. 347-356
  
• Abraham Flaxman:
  A spectral technique for random satisfiable 3CNF formulas. 357-363
  
• Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin:
  Random MAX SAT, random MAX CUT, and their phase transitions. 364-373
  

Session 5C

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

Session 6: invited plenary abstract

• S. Muthukrishnan:
  Data streams: algorithms and applications. 413-413
  

Session 7A

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

Session 7B

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

Session 7C

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

Session 8A

• Ashish Goel, Deborah Estrin:
  Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. 499-505
  
• Benjamin Doerr:
  Non-independent randomized rounding. 506-507
  
• Nikhil Bansal, Kedar Dhamdhere:
  Minimizing weighted flow time. 508-516
  
• 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
  

Session 8B

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

Session 8C

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

Session 9A

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

Session 9B

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

Session 9C

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

Session 10: invited plenary abstract

• Persi Diaconis:
  Who cares about permanents? 708-708
  

Session 11A

• Dieter Kratsch, Jeremy Spinrad:
  Between O(nm) and O(n alpha). 709-716
  
• 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
  
• Raja Jothi, Balaji Raghavachari, Subramanian Varadarajan:
  A 5/4-approximation algorithm for minimum 2-edge-connectivity. 725-734
  
• Chaitanya Swamy, David B. Shmoys:
  Fault-tolerant facility location. 735-736
  

Session 11B

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

Session 11C

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

Session 12A

• Mihai Badoiu, Kenneth L. Clarkson:
  Smaller core-sets for balls. 801-802
  
• Leonidas J. Guibas, An Nguyen, Li Zhang:
  Zonotopes as bounding volumes. 803-812
  
• 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
  
• Adrian Dumitrescu:
  An approximation algorithm for cutting out convex polygons. 823-827
  

Session 12B

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

Session 12C

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

Last update Thu May 23 06:19:51 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page