default search action
12th SODA 2001: Washington, DC, USA
- S. Rao Kosaraju:
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA. ACM/SIAM 2001, ISBN 0-89871-490-7 - Eran Halperin, Uri Zwick:
Combinatorial approximation algorithms for the maximum directed cut problem. 1-7 - Gruia Calinescu, Howard J. Karloff, Yuval Rabani:
Approximation algorithms for the 0-extension problem. 8-16 - Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat:
A faster implementation of the Goemans-Williamson clustering algorithm. 17-25 - Joseph Naor, Yuval Rabani:
Tree packing and approximating k-cuts. 26-27 - Xiang-Yang Li, Shang-Hua Teng:
Generating well-shaped Delaunay meshed in 3D. 28-37 - Adrian Dumitrescu, Joseph S. B. Mitchell:
Approximation algorithms for TSP with neighborhoods in the plane. 38-46 - Ho-Lun Cheng, Tamal K. Dey, Herbert Edelsbrunner, John Sullivan:
Dynamic skin triangulation. 47-56 - Sariel Har-Peled
, Micha Sharir:
Online point location in planar arrangements and its applications. 57-66 - Peter Sanders:
Reconciling simplicity and realism in parallel disk models. 67-76 - Jeffrey Scott Vitter, David A. Hutchinson:
Distribution sort with randomizing cycle. 77-86 - Ulrich Meyer:
External memory BFS on undirected graphs with bounded degree. 87-88 - Anil Maheshwari, Norbert Zeh:
I/O-efficient algorithms for graphs of bounded treewidth. 89-90 - Noga Alon, Benny Sudakov, Uri Zwick:
Constructing worst case instances for semidefinite programming based approximation algorithms. 92-100 - Marco Pellegrini:
Randomizing combinatorial algorithms for linear programming when the dimension is moderately high. 101-108 - Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin:
Approximation algorithms for the metric labeling problem via a new linear programming formulation. 109-118 - Benjamin Doerr:
Lattice approximation and linear discrepency of totally unimodular matrices. 119-125 - Ravi Kumar, D. Sivakumar:
On polynomial approximation to the shortest lattice vector length. 126-127 - Francis Y. L. Chin, Stanley P. Y. Fung, Cao An Wang:
Approximation for minimum triangulation of convex polyhedra. 128-137 - Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia:
Optimal covering tours with turn costs. 138-147 - Pankaj K. Agarwal, Sariel Har-Peled
Maintaining approximate extent measures of moving points. 148-157 - John Hershberger, Subhash Suri:
Simplified kinetic connectivity for rectangles and hypercubes. 158-167 - Menelaos I. Karavelas, Leonidas J. Guibas:
Static and kinetic geometric spanners with applications. 168-176 - David Liben-Nowell:
Gossip is synteny: incomplete gossip and an exact algorithm for syntenic distance. 177-185 - Tandy J. Warnow, Bernard M. E. Moret, Katherine St. John:
Absolute convergence: true trees from short sequences. 186-195 - Katherine St. John, Tandy J. Warnow, Bernard M. E. Moret, Lisa Vawter:
Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining. 196-205 - Daniel G. Brown:
A probabilistic analysis of a greedy algorithm arising from computational biology. 206-207 - Rahul Shah, Martin Farach-Colton:
On the midpath tree conjuncture: a counter-example. 208-209 - Cyril Gavoille, David Peleg, Stephane Perennes, Ran Raz
Distance labeling in graphs. 210-219 - Anupam Gupta:
Steiner points in tree metrics don't (really) help. 220-227 - David Eppstein, Joseph Wang:
Fast approximation of centrality. 228-229 - Guangting Chen, Guoliang Xue:
K-pair delay constrained minimum cost routing in undirected networks. 230-231 - Chandra Chekuri, Sanjeev Khanna, Joseph Naor:
A deterministic algorithm for the cost-distance problem. 232-233 - Yunhong Zhou, Subhash Suri:
Shape sensitive geometric permutations. 234-243 - Yingping Huang, Jinhui Xu, Danny Z. Chen:
Geometric permutations of high dimensional spheres. 244-245 - Carsten Gutwenger, Petra Mutzel, René Weiskircher:
Inserting an edge into a planar graph. 246-255 - Sunil Arya, Theocharis Malamatos, David M. Mount:
Entropy-preserving cuttings and space-efficient planar point location. 256-261 - Sunil Arya, Theocharis Malamatos, David M. Mount:
A simple entropy-based algorithm for planar point location. 262-268 - Paolo Ferragina, Giovanni Manzini:
An experimental study of an opportunistic index. 269-278 - Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat:
Overlap matching. 279-288 - Erik D. Demaine, Alejandro López-Ortiz:
A linear lower bound on index size for text retrieval. 289-294 - Alon Efrat, Piotr Indyk, Suresh Venkatasubramanian:
Pattern matching for sets of segments. 295-304 - Amihood Amir, Ely Porat, Moshe Lewenstein:
Approximate subset matching with Don't Cares. 305-306 - Arne Andersson, Mikkel Thorup:
Dynamic string searching. 307-308 - Guy Kortsarz, Robert Krauthgamer:
On approximating the achromatic number. 309-318 - Eran Halperin, Ram Nathaniel, Uri Zwick:
Coloring k-colorable graphs using smaller palettes. 319-326 - Michael Krivelevich, Ram Nathaniel, Benny Sudakov:
Approximating coloring and maximum independent sets in 3-uniform hypergraphs. 327-328 - David Eppstein:
Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. 329-337 - Mirela Damian-Iordache, Sriram V. Pemmaraju:
Computing optimal alpha-fat and alpha-small decompositions. 338-339 - John Iacono:
Optimal planar point location. 340-341 - Danny Z. Chen, Ovidiu Daescu, John Hershberger, Peter M. Kogge, Jack Snoeyink:
Polygonal path approximation with angle constraints. 342-343 - Stefan Funke, Edgar A. Ramos:
Reconstructing a collection of curves with corners and endpoints. 344-353 - Adam Meyerson, Kamesh Munagala, Serge A. Plotkin:
Web caching using access statistics. 354-363 - Amotz Bar-Noy, Richard E. Ladner
Competitive on-line stream merging algorithms for media-on-demand. 364-373 - Mark Brehob, Richard J. Enbody, Eric Torng, Stephen Wagner:
On-line restricted caching. 374-383 - Ashish Goel, Adam Meyerson, Serge A. Plotkin:
Approximate majorization and fair online load balancing. 384-390 - Christos H. Papadimitriou:
Game theory, algorithms, and the Internet. 391 - David R. Karger, Nathan Srebro:
Learning Markov networks: maximum bounded tree-width graphs. 392-401 - Dieter Rautenbach, Bruce A. Reed:
Approximately covering by cycles in planar graphs. 402-406 - Alexander Zelikovsky, Ion I. Mandoiu:
Practical approximation algorithms for zero- and bounded-skew trees. 407-416 - Adrian Vetta:
Approximating the minimum strongly connected subgraph via a matching lower bound. 417-426 - Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, Suneeta Ramaswami:
Improved approximation algorithms for rectangle tiling and packing. 427-436 - Nina Mishra, Daniel Oblinger, Leonard Pitt:
Sublinear time approximate clustering. 439-447 - Moni Naor, Benny Pinkas:
Efficient oblivious transfer protocols. 448-457 - Moni Naor, Omer Reingold:
Constructing pseudo-random permutations with a prescribed structure. 458-459 - Vijay Raghavan, Jeremy P. Spinrad:
Robust algorithms for restricted domains. 460-467 - Daniel Kobler, Udi Rotics:
Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract). 468-476 - Julie L. Johnson, Jeremy P. Spinrad:
A polynomial time recognition algorithm for probe interval graphs. 477-486 - Johann A. Makowsky:
Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width. 487-495 - Chen Li, Chee-Keng Yap:
A new constructive root bound for algebraic expressions. 496-505 - Yi-Ting Chiang, Ching-Chi Lin, Hsueh-I Lu:
Orderly spanning trees with applications to graph encoding and graph drawing. 506-515 - John Iacono:
Alternatives to splay trees with O(log n) worst-case access times. 516-522 - Andrej Brodnik, Svante Carlsson, Johan Karlsson, J. Ian Munro:
Worst case constant time priority queue. 523-528 - J. Ian Munro, Venkatesh Raman, Adam J. Storm:
Representing dynamic binary trees succinctly. 529-536 - Amos Fiat, Haim Kaplan:
Making data structures confluently persistent. 537-546 - Serge Abiteboul, Haim Kaplan, Tova Milo:
Compact labeling schemes for ancestor queries. 547-556 - János Csirik, David S. Johnson, Claire Kenyon:
Better approximation algorithms for bin covering. 557-566 - Aravind Srinivasan:
New approaches to covering and packing problems. 567-576 - Daniel W. Engels, Jon Feldman, David R. Karger, Matthias Ruhl:
Parallel processor scheduling with delay constraints. 577-585 - Edward G. Coffman Jr., George S. Lueker:
Approximation algorithms for extensible bin packing. 586-588 - Martin Skutella, Marc Uetz:
Scheduling precedence-constrained jobs with stochastic processing times on parallel machines. 589-590 - Alexander Kesselman, Yishay Mansour:
Loss-bounded analysis for differentiated services. 591-600 - Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Stability preserving transformations: packet routing networks with edge capacities and speeds. 601-610 - Ashish Goel, Adam Meyerson, Serge A. Plotkin:
Distributed admission control, scheduling, and routing with stale information. 611-619 - Joseph Hall, Jason D. Hartline, Anna R. Karlin, Jared Saia, John Wilkes:
On algorithms for efficient data migration. 620-629 - Gianluca De Marco, Andrzej Pelc:
Fast distributed graph coloring with O(Delta) colors. 630-635 - Sudipto Guha, Adam Meyerson, Kamesh Munagala:
Improved algorithms for fault tolerant facility location. 636-641 - Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan:
Algorithms for facility location problems with outliers. 642-651 - Alan M. Frieze, Gregory B. Sorkin:
The probabilistic relationship between the assignment and asymmetric traveling salesman problems. 652-660 - Ivan D. Baev, Rajmohan Rajaraman:
Approximation algorithms for data placement in arbitrary networks. 661-670 - Thomas Erlebach, Klaus Jansen, Eike Seidel:
Polynomial-time approximation schemes for geometric graphs. 671-679 - Alon Efrat, Sariel Har-Peled
Morphing between polylines. 680-689 - Kim Miller, Suneeta Ramaswami, Peter J. Rousseeuw, Joan Antoni Sellarès, Diane L. Souvaine, Ileana Streinu, Anja Struyf:
Fast implementation of depth contours using topological sweep. 690-699 - Marshall W. Bern:
Computing the depth of a flat. 700-701 - Hana Chockler, Uri Zwick:
Which formulae shrink under random restrictions? 702-708 - Andrea E. F. Clementi, Angelo Monti, Riccardo Silvestri:
Selective families, superimposed codes, and broadcasting on unknown radio networks. 709-718 - Gabriel Istrate, Madhav V. Marathe, S. S. Ravi:
Adversarial models in evolutionary game dynamics. 719-720 - Dimitris Achlioptas, Arthur D. Chtcherba, Gabriel Istrate, Cristopher Moore:
The phase transition in 1-in-k SAT and NAE 3-SAT. 721-722 - Fan R. K. Chung, Ronald L. Graham, Frank Thomson Leighton:
Guessing secrets. 723-726 - Gopal Pandurangan, Eli Upfal:
Can entropy characterize performance of online algorithms?. 727-734 - Andrew V. Goldberg, Jason D. Hartline, Andrew Wright:
Competitive auctions and digital goods. 735-744 - James Aspnes, David F. Fischer, Michael J. Fischer, Ming-Yang Kao, Alok Kumar:
Towards understanding the predictability of stock markets from the perspective of computational complexity. 745-754 - Tak Wah Lam, Kar-Keung To:
Performance guarentee for online deadline scheduling in the presence of overload. 755-764 - Gerhard J. Woeginger:
Assigning chain-like tasks to a chain-like network. 765-766 - Richard J. Anderson, Brian Tjaden:
The inverse nearest neighbor problem with astrophysical applications. 767-768 - Ashish Goel, Piotr Indyk, Kasturi R. Varadarajan:
Reductions among high dimensional proximity problems. 769-778 - Stephen Alstrup, Thore Husfeldt, Theis Rauhe:
A cell probe lower bound for dynamic nearest-neighbor searching. 779-780 - Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia:
Shape matching using edit-distance: an implementation. 781-790 - Vida Dujmovic, Sue Whitesides:
On validating planar worlds. 791-792 - Yijie Han:
Improved fast integer sorting in linear space. 793-796 - Ulrich Meyer:
Single-source shortest-paths on arbitrary directed graphs in linear average-case time. 797-806 - Christian A. Duncan, Stephen G. Kobourov, V. S. Anil Kumar:
Optimal constrained graph exploration. 807-814 - Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel:
An efficient algorithm for the configuration problem of dominance graphs. 815-824 - Therese Biedl:
Linear reductions of maximum matching. 825-826 - David Eppstein, S. Muthukrishnan:
Internet packet filter management and rectangle geometry. 827-835 - Haim Kaplan, Robert Endre Tarjan, Kostas Tsioutsiouliklis:
Faster kinetic heaps and their use in broadcast scheduling. 836-844 - Michael A. Bender, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin:
Finding least common ancestors in directed acyclic graphs. 845-854 - Eduardo Sany Laber, Ruy Luiz Milidiú, Artur Alves Pessoa:
On binary searching with non-uniform costs. 855-864 - Artur Czumaj, Christian Sohler
Soft kinetic data structures. 865-872 - Eldar Fischer:
Testing graphs for colorable properties. 873-882 - Alon Amit, Nathan Linial, Jirí Matousek, Eyal Rozenman:
Random lifts of graphs. 883-894 - Justin A. Boyan, Michael Mitzenmacher:
IMproved results for route planning in stochastic transportation. 895-902 - Ted Carson, Russell Impagliazzo:
Hill-climbing finds random planted bisections. 903-909 - Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
On universally easy classes for NP-complete problems. 910-911 - Linyuan Lu:
The diameter of random massive graphs. 912-921 - Aravind Srinivasan:
Domatic partitions and the Lovász local lemma. 922-923 - Sriram V. Pemmaraju:
Equitable colorings extend Chernoff-Hoeffding bounds. 924-925 - Yevgeniy Dodis, Peter Winkler:
Universal configurations in light-flipping games. 926-927 - Jérémy Barbay, Claire Kenyon:
On the discrete Bak-Sneppen model of self-organized criticality. 928-933
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-02-18 01:00 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: