default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID13th SODA 2002: San Francisco, CA, USA
- David Eppstein:
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA. ACM/SIAM 2002, ISBN 0-89871-513-X - Avrim Blum, Shuchi Chawla, Adam Kalai:
Static optimality and dynamic search-optimality in lists and trees. 1-8 - Rasmus Pagh, Jakob Pagter:
Optimal time-space trade-offs for non-comparison-based sorting. 9-18 - Haim Kaplan, Nira Shafrir, Robert Endre Tarjan:
Union-find with deletions. 19-28 - Michael A. Bender, Ziyang Duan, John Iacono, Jing Wu:
A locality-preserving cache-oblivious dynamic dictionary. 29-38 - Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob:
Cache oblivious search trees via binary trees of small height. 39-48 - Guy Even, Guy Kortsarz:
An approximation algorithm for the group Steiner problem. 49-58 - Leonid Zosin, Samir Khuller:
On directed Steiner trees. 59-63 - Markus Bläser:
An 8/13-approximation algorithm for the asymmetric maximum TSP. 64-73 - Béla Csaba, Marek Karpinski, Piotr Krysta:
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. 74-83 - Harold N. Gabow:
An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph. 84-93 - Amos Fiat, Jared Saia:
Censorship resistant peer-to-peer content addressable networks. 94-103 - Tomás Feder, Rajeev Motwani, Rina Panigrahy, An Zhu:
Web caching with request reordering. 104-105 - Sudipto Guha, Kamesh Munagala:
Improved algorithms for the data placement problem. 106-107 - Rahul Shah, Martin Farach-Colton:
Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees. 108-115 - Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev:
Temporary tasks assignment resolved. 116-124 - Jeff Erickson:
Dense point sets have sparse Delaunay triangulations: or "... but not too nasty". 125-134 - Sunghee Choi, Nina Amenta:
Delaunay triangulation programs on surface data. 135-136 - Siu-Wing Cheng, Tamal K. Dey:
Quality meshing with weighted Delaunay refinement. 137-146 - Sunil Arya, Theocharis Malamatos:
Linear-size approximate voronoi diagrams. 147-155 - Siu-Wing Cheng, Antoine Vigneron:
Motorcycle graphs and straight skeletons. 156-165 - George Karakostas:
Faster approximation schemes for fractional multicommodity flow problems. 166-173 - Ekkehard Köhler, Martin Skutella:
Flows over time with load-dependent transit times. 174-183 - Petr Kolman, Christian Scheideler:
Improved bounds for the unsplittable flow problem. 184-193 - Thomas Erlebach, Alexander Hall:
NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. 194-202 - Tim Roughgarden:
How unfair is optimal routing? 203-204 - Eric Lehman, Abhi Shelat:
Approximation algorithms for grammar-based compression. 205-212 - Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo:
Improving table compression with combinatorial optimization. 213-222 - Hsueh-I Lu:
Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. 223-224 - Kunihiko Sadakane:
Succinct representations of lcp information and improvements in the compressed suffix arrays. 225-232 - Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao:
Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. 233-242 - Uri Zwick:
Jenga. 243-246 - Fan R. K. Chung, Ronald L. Graham, Linyuan Lu:
Guessing secrets with inner product questions. 247-253 - Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding. 254-262 - Sven Oliver Krumke, Maarten Lipmann, Willem de Paepe, Diana Poensgen, Jörg Rambau, Leen Stougie, Gerhard J. Woeginger:
How to cut a cake almost fairly. 263-264 - Giovanni Rinaldi, Ulrich Voigt, Gerhard J. Woeginger:
The mathematics of playing golf. 265-266 - Seth Pettie, Vijaya Ramachandran:
Computing shortest paths with comparisons and additions. 267-276 - Yoshiharu Kohayakawa, Vojtech Rödl, Lubos Thoma:
An optimal algorithm for checking regularity (extended abstract). 277-286 - Ojas Parekh:
Edge dominating and hypomatchable sets. 287-291 - Vilhelm Dahllöf, Peter Jonsson:
An algorithm for counting maximum weighted independent sets and its applications. 292-298 - Ryan Williams:
Algorithms for quantified Boolean formulas. 299-307 - Eleni Drinea, Alan M. Frieze, Michael Mitzenmacher:
Balls and bins models with feedback. 308-315 - Colin Cooper, Alan M. Frieze, Gregory B. Sorkin:
A note on random 2-SAT with prescribed literal degrees. 316-320 - Igor Pak:
Mixing time and long paths in graphs. 321-328 - Don Coppersmith, David Gamarnik, Maxim Sviridenko:
The diameter of a long range percolation graph. 329-337 - Cédric Adjih, Leonidas Georgiadis, Philippe Jacquet, Wojciech Szpankowski:
Is the internet fractal? 338-345 - Victor Chepoi, Feodor F. Dragan, Yann Vaxès:
Center and diameter problems in plane triangulations and quadrangulations. 346-355 - Seok-Hee Hong, Brendan D. McKay, Peter Eades:
Symmetric drawings of triconnected planar graphs. 356-365 - Shimon Even, Roni Kupershtok:
Layout area of the hypercube (extended abstract). 366-371 - Anil Maheshwari, Norbert Zeh:
I/O-optimal algorithms for planar graphs using separators. 372-381 - Ryan B. Hayward, Stefan Hougardy, Bruce A. Reed:
Polynomial time recognition of P4-structure. 382-389 - Jérémy Barbay, Claire Kenyon:
Adaptive intersection and t-threshold problems. 390-399 - Amihood Amir, Kenneth Ward Church, Emanuel Dar:
Separable attributes: a technique for solving the sub matrices character count problem. 400-401 - Cristopher Moore, Ivan Rapaport, Eric Rémila:
Tiling groups for Wang tiles. 402-411 - Adam Kalai:
Generating random factored numbers, easily. 412-412 - Artur Czumaj, Berthold Vöcking:
Tight bounds for worst-case equilibria. 413-420 - Jeff Edmonds, Kirk Pruhs:
Broadcast scheduling: when fairness is fine. 421-430 - Lars Engebretsen, Madhu Sudan:
Harmonic broadcasting is optimal. 431-432 - Amotz Bar-Noy, Richard E. Ladner
:
Windows scheduling problems for broadcast systems. 433-442 - Matthew Andrews, Lisa Zhang:
Scheduling protocols for switches with large envelopes. 443-452 - Alon Efrat, Frank Hoffmann, Christian Knauer, Klaus Kriegel, Günter Rote, Carola Wenk:
Covering shapes by ellipses. 453-454 - Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan:
Slice and dice: a simple, improved approximate tiling recipe. 455-464 - Csaba D. Tóth:
Binary space partitions for line segments with a limited number of directions. 465-471 - Timothy M. Chan:
Closest-point problems simplified on the RAM. 472-473 - Timothy M. Chan:
Semi-online maintenance of geometric optima and measures. 474-483 - Sudipto Guha, Kamesh Munagala:
Generalized clustering. 484-485 - Steven S. Seiden, Rob van Stee:
New bounds for multi-dimensional packing. 486-495 - Uri Zwick:
Computer assisted proof of optimal approximability results. 496-505 - Eran Halperin, Dror Livnat, Uri Zwick:
MAX CUT in cubic graphs. 506-513 - Piotr Berman, Marek Karpinski:
Approximating minimum unsatisfiability of linear equations. 514-516 - Sandy Irani, Xiangwen Lu, Amelia Regan:
On-line algorithms for the dynamic traveling repair problem. 517-524 - Amotz Bar-Noy, Ari Freund, Shimon Landa, Joseph Naor:
Competitive on-line switching policies. 525-534 - Sanjeev Arora, Bo Brinkman:
A randomized online algorithm for bandwidth utilization. 535-539 - Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi:
Caching with expiration times. 540-547 - Edward J. Anderson, Chris N. Potts:
On-line scheduling of a single machine to minimize total weighted completion time. 548-557 - Shankar Krishnan, Nabil H. Mustafa, Suresh Venkatasubramanian:
Hardware-assisted computation of depth contours. 558-567 - Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, Martin Skutella:
The freeze-tag problem: how to wake up a swarm of robots. 568-577 - Darin Goldstein, Nick Meyer:
The wake up and report problem is time-equivalent to the firing squad synchronization problem. 578-587 - Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, Andrzej Pelc:
Tree exploration with little memory. 588-597 - József Beck, Sachin Lodha:
Efficient proper 2-coloring of almost disjoint hypergraphs. 598-605 - Irene Finocchi, Alessandro Panconesi, Riccardo Silvestri:
Experimental analysis of simple, distributed vertex coloring algorithms. 606-615 - Moses Charikar:
On semidefinite programming relaxations for graph coloring and vertex cover. 616-620 - R. Ravi, Amitabh Sinha II:
Approximating k-cuts via network strength. 621-622 - Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar:
Reductions in streaming algorithms, with an application to counting triangles in graphs. 623-632 - Brian Babcock, Mayur Datar, Rajeev Motwani:
Sampling from a moving window over streaming data. 633-634 - Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani:
Maintaining stream statistics over sliding windows (extended abstract). 635-644 - Noga Alon, Asaf Shapira:
Testing satisfiability. 645-654 - Adam Kalai:
Efficient pattern-matching with don't cares. 655-656 - S. Muthukrishnan:
Efficient algorithms for document retrieval problems. 657-666 - Graham Cormode, S. Muthukrishnan:
The string edit distance matching problem with moves. 667-676 - Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan:
Simple approximation algorithm for nonoverlapping local alignments. 677-678 - Maxime Crochemore, Gad M. Landau, Michal Ziv-Ukelson:
A sub-quadratic sequence alignment algorithm for unrestricted cost matrices. 679-688 - Leszek Gasieniec, Andrzej Lingas:
On adaptive deterministic gossiping in ad hoc radio networks. 689-690 - Alexander Gamburd, Igor Pak:
Expansion of product replacement graphs. 691-696 - Piotr Indyk:
Explicit constructions of selectors and related combinatorial structures, with applications. 697-704 - Lars Engebretsen, Piotr Indyk, Ryan O'Donnell:
Derandomized dimensionality reduction with applications. 705-712 - Seth Pettie, Vijaya Ramachandran:
Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. 713-722 - April Rasala, Clifford Stein, Eric Torng, Patchrawat Uthaisombut:
Existence theorems, lower bounds and algorithms for scheduling to meet two objectives. 723-731 - Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira:
Scheduling split intervals. 732-741 - Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai:
Throughput maximization of real-time scheduling with batching. 742-751 - Allan Borodin, Morten N. Nielsen, Charles Rackoff:
(Incremental) priority algorithms. 752-761 - Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman:
Improved algorithms for stretch scheduling. 762-771 - Tamal K. Dey, Joachim Giesen, Samrat Goswami, Wulue Zhao:
Shape dimension and approximation from samples. 772-780 - Stefan Funke, Edgar A. Ramos:
Smooth-surface reconstruction in near-linear time. 781-790 - Pankaj K. Agarwal, Herbert Edelsbrunner, Yusu Wang:
Computing the writhing number of a polygonal knot. 791-799 - Pankaj K. Agarwal, Micha Sharir:
Pseudo-line arrangements: duality, algorithms, and applications. 800-809 - Vladlen Koltun, Micha Sharir:
On the overlay of envelopes in four dimensions. 810-819 - Philip N. Klein:
Preprocessing an undirected planar network to enable fast approximate distance queries. 820-827 - Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid:
Approximate distance oracles for geometric graphs. 828-837 - Camil Demetrescu, Mikkel Thorup:
Oracles for distances avoiding a link-failure. 838-843 - Liam Roditty, Mikkel Thorup, Uri Zwick:
Roundtrip spanners and roundtrip routing in directed graphs. 844-851 - Michelangelo Grigni, Papa A. Sissokho:
Light spanners and approximate TSP in weighted graphs with forbidden minors. 852-857 - Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or:
Capacitated vertex covering with applications. 858-865 - Ross M. McConnell, Jeremy P. Spinrad:
Construction of probe interval models. 866-875 - Alantha Newman:
A new algorithm for protein folding in the HP model. 876-884 - David Hart:
An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing. 885-893 - Gianluca Della Vedova, Tao Jiang, Jing Li, Jianjun Wen:
Approximating minimum quartet inconsistency (abstract). 894-895 - Tetsuo Asano, Naoki Katoh, Koji Obokata, Takeshi Tokuyama:
Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning. 896-904 - Avrim Blum, John Dunagan:
Smoothed analysis of the perceptron algorithm for linear programming. 905-914 - Satoru Iwata:
A fully combinatorial algorithm for submodular function minimization. 915-919 - Friedrich Eisenbrand, Giovanni Rinaldi, Paolo Ventura:
0/1 optimization and 0/1 primal separation are equivalent. 920-926 - Michal Katz, Nir A. Katz, Amos Korman, David Peleg:
Labeling schemes for flow and connectivity. 927-936 - Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick:
Reachability and distance queries via 2-hop labels. 937-946 - Stephen Alstrup, Theis Rauhe:
Improved labeling scheme for ancestor queries. 947-953 - Haim Kaplan, Tova Milo, Ronen Shabo:
A comparison of labeling schemes for ancestor queries. 954-963 - Ziv Bar-Yossef, Kirsten Hildrum, Felix Wu:
Incentive-compatible online auctions for digital goods. 964-970 - Avrim Blum, Tuomas Sandholm, Martin Zinkevich:
Online algorithms for market clearing. 971-980 - Micah Adler, Dan Rubenstein:
Pricing multicasting in more practical network models. 981-990 - Aaron Archer, Éva Tardos:
Frugal path mechanisms. 991-999 - R. Ravi, David P. Williamson:
Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems. 1000-1001
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 2025-11-13 22:04 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:
