default search action
14th SODA 2003: Baltimore, Maryland, USA
- Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA. ACM/SIAM 2003, ISBN 0-89871-538-5
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 G. Pittel:
Perfect matchings in random graphs with prescribed minimal degree. 148-157
Session 3C
- Dieter Kratsch, Ross M. McConnell, Kurt Mehlhorn, Jeremy P. 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 D. 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 AC0 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 P. 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 E. 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
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 Thanh 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-14 20:47 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: