13. SODA 2002: San Francisco, CA, USA

• 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
  
• Cedric 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 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 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
  

Last update Sat May 18 19:48:57 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page