12. SODA 2001: Washington, DC, USA

• 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 Warnow, Bernard M. E. Moret, Katherine St. John:
  Absolute convergence: true trees from short sequences. 186-195
  
• Katherine St. John, Tandy 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 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 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, Leonidas J. Guibas, T. M. Murali:
  Morphing between polylines. 680-689
  
• Kim Miller, Suneeta Ramaswami, Peter 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 C. 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
  

Last update Fri May 24 19:50:52 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page