16. SODA 2005: Vancouver, BC, Canada

Session 1A

• Daniel K. Blandford, Guy E. Blelloch:
  Dictionaries using variable-length keys and data, with applications. 1-10
  
• Peter Bro Miltersen:
  Lower bounds on the size of selection and rank indexes. 11-12
  
• Ho-Leung Chan, Wing-Kai Hon, Tak Wah Lam, Kunihiko Sadakane:
  Dynamic dictionary matching and compressed suffix trees. 13-22
  
• Meng He, J. Ian Munro, S. Srinivasa Rao:
  A categorization theorem on suffix arrays with applications to space efficient text indexes. 23-32
  
• GaHyun Park, Wojciech Szpankowski:
  Towards a complete characterization of tries. 33-42
  

Session 1B

• James Aspnes, Kevin L. Chang, Aleksandr Yampolskiy:
  Inoculation strategies for victims of viruses and the sum-of-squares partition problem. 43-52
  
• Nicole Immorlica, Mohammad Mahdian:
  Marriage, honesty, and stability. 53-62
  
• Kamal Jain, Vijay V. Vazirani, Yinyu Ye:
  Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. 63-71
  
• Bruno Codenotti, Sriram V. Pemmaraju, Kasturi R. Varadarajan:
  On the polynomial time computation of equilibria for certain exchange economies. 72-81
  
• Christos H. Papadimitriou, Tim Roughgarden:
  Computing equilibria in multi-player games. 82-91
  

Session 1C

• James R. Lee:
  On distance scales, embeddings, and efficient relaxations of the cut cone. 92-101
  
• Shuchi Chawla, Anupam Gupta, Harald Räcke:
  Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. 102-111
  
• Christos H. Papadimitriou, Shmuel Safra:
  The complexity of low-distortion embeddings between point sets. 112-118
  
• Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, Anastasios Sidiropoulos:
  Approximation algorithms for low-distortion embeddings into low-dimensional spaces. 119-128
  
• Moses Charikar, Adriana Karagiozova:
  A tight threshold for metric Ramsey phenomena. 129-136
  

Invited Plenary Abstract

• Micha Sharir:
  The interface between computational and combinatorial geometry. 137-145
  

Session 3A

• Philip N. Klein:
  Multiple-source shortest paths in planar graphs. 146-155
  
• Andrew V. Goldberg, Chris Harrelson:
  Computing the shortest path: A search meets graph theory. 156-165
  
• Tomás Feder, Rajeev Motwani:
  Finding large cycles in Hamiltonian graphs. 166-175
  
• Zeev Nutov:
  Approximating connectivity augmentation problems. 176-185
  
• László A. Végh, András A. Benczúr:
  Primal-dual approach for directed vertex connectivity augmentation and generalizations. 186-194
  

Session 3B

• Andrei Z. Broder, Michael Mitzenmacher:
  Multidimensional balanced allocations. 195-196
  
• Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton:
  Online client-server load balancing without global information. 197-206
  
• Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko:
  Job shop scheduling with unit processing times. 207-214
  
• Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor:
  Approximating the average response time in broadcast scheduling. 215-221
  
• Michael Elkin, Guy Kortsarz:
  Improved schedule for radio broadcast. 222-231
  

Session 3C

• Timothy M. Chan:
  On levels in arrangements of surfaces in three dimensions. 232-240
  
• Hanno Lefmann:
  Distributions of points in the unit-square and large k-gons. 241-250
  
• Boris Aronov, Shakhar Smorodinsky:
  On geometric permutations induced by lines transversal through a fixed point. 251-256
  
• Miroslav Chlebík, Janka Chlebíková:
  Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes. 267-276
  

Session 4A

• Robert D. Kleinberg, Jon M. Kleinberg:
  Isomorphism and embedding problems for infinite limits of scale-free graphs. 277-286
  
• Abraham Flaxman, Alan M. Frieze, Juan Vera:
  Adversarial deletion in a scale free random graph process. 287-292
  
• Soumen Chakrabarti, Alan M. Frieze, Juan Vera:
  The influence of search engines on preferential attachment. 293-300
  
• Noam Berger, Christian Borgs, Jennifer T. Chayes, Amin Saberi:
  On the spread of viruses on the internet. 301-310
  
• Van Nguyen, Charles U. Martel:
  Analyzing and characterizing small-world graphs. 311-320
  

Session 4B

• Graham Cormode, S. Muthukrishnan:
  Substring compression problems. 321-330
  
• Stefan Gumhold:
  Optimizing markov models with applications to triangular connectivity coding. 331-338
  
• Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini:
  Dotted interval graphs and high throughput genotyping. 339-348
  
• Jesper Jansson, Nguyen Bao Nguyen, Wing-Kin Sung:
  Algorithms for combining rooted triplets into a galled phylogenetic network. 349-358
  
• Masao Hara, Seiichi Tani, Makoto Yamamoto:
  Unknotting is in AM cup co-AM. 359-364
  

Session 4C

• Retsef Levi, Robin Roundy, David B. Shmoys:
  A constant approximation algorithm for the one-warehouse multi-retailer problem. 365-374
  
• Luca Becchetti, Jochen Könemann, Stefano Leonardi, Martin Pál:
  Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. 375-384
  
• Abraham Flaxman, Adam Tauman Kalai, H. Brendan McMahan:
  Online convex optimization in the bandit setting: gradient descent without a gradient. 385-394
  
• Brian C. Dean, Michel X. Goemans, Jan Vondrák:
  Adaptivity and approximation for stochastic packing problems. 395-404
  
• Anthony Man-Cho So, Yinyu Ye:
  Theory of semidefinite programming for sensor network localization. 405-414
  

Session 5A

• Marcelo H. de Carvalho, Joseph Cheriyan:
  An O(VE) algorithm for ear decompositions of matching-covered graphs. 415-423
  
• David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn:
  Popular matchings. 424-432
  
• Loukas Georgiadis, Robert Endre Tarjan:
  Dominator tree verification and vertex-disjoint paths. 433-442
  
• Irit Katriel, Hans L. Bodlaender:
  Online topological ordering. 443-450
  
• David Eppstein:
  All maximal independent sets and dynamic dominance for sparse graphs. 451-459
  

Session 5B

• Jon Feldman, Clifford Stein:
  LP decoding achieves capacity. 460-469
  
• Venkatesan Guruswami, Alexander Vardy:
  Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. 470-478
  
• Micah Adler:
  Collecting correlated information from a sensor network. 479-488
  
• Nicholas J. A. Harvey, David R. Karger, Kazuo Murota:
  Deterministic network coding by matrix completion. 489-498
  
• April Rasala Lehman, Eric Lehman:
  Network coding: does the model need tuning? 499-504
  

Session 5C

• Vladlen Koltun:
  Pianos are not flat: rigid motion planning in three dimensions. 505-514
  
• Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell:
  A constant-factor approximation algorithm for optimal terrain guarding. 515-524
  
• Micha Sharir, Hayim Shaul:
  Ray shooting amid balls, farthest point from a line, and range emptiness searching. 525-534
  
• Sunil Arya, Theocharis Malamatos, David M. Mount:
  Space-time tradeoffs for approximate spherical range counting. 535-544
  
• Amos Fiat, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl:
  Online conflict-free coloring for intervals. 545-554
  

Invited Plenary Abstract

• John C. Baez:
  Loop quantum gravity. 555
  

Session 7A

• Michael Krivelevich, Zeev Nutov, Raphael Yuster:
  Approximation algorithms for cycle packing problems. 556-561
  
• Harold N. Gabow, Michel X. Goemans, Éva Tardos, David P. Williamson:
  Approximating the smallest k-edge connected spanning subgraph by LP-rounding. 562-571
  
• Özgür Sümer:
  Partial covering of hypergraphs. 572-581
  
• Tomokazu Imamura, Kazuo Iwama:
  Approximating vertex cover on dense graphs. 582-589
  
• Erik D. Demaine, Mohammad Taghi Hajiaghayi:
  Bidimensionality: new connections between FPT algorithms and PTASs. 590-601
  

Session 7B

• Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni:
  Limitations of cross-monotonic cost sharing schemes. 602-611
  
• Jochen Könemann, Stefano Leonardi, Guido Schäfer:
  A group-strategyproof mechanism for Steiner forests. 612-619
  
• Andrew V. Goldberg, Jason D. Hartline:
  Collusion-resistant mechanisms for single-parameter agents. 620-629
  
• Robert D. Kleinberg:
  A multiple-choice secretary algorithm with applications to online auctions. 630-631
  
• Navin Goyal, Michael E. Saks:
  Rounds vs queries trade-off in noisy computation. 632-639
  

Session 7C

• Aleksandrs Slivkins:
  Distributed approaches to triangulation and embedding. 640-649
  
• Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos:
  Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. 650-659
  
• Don Coppersmith, Michael Elkin:
  Sparse source-wise and pair-wise distance preservers. 660-669
  
• Pankaj K. Agarwal, Yusu Wang, Peng Yin:
  Lower bound for sparse Euclidean spanners. 670-671
  
• Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie:
  New constructions of (alpha, beta)-spanners and purely additive spanners. 672-681
  

Session 8A

• Erik D. Demaine, Mohammad Taghi Hajiaghayi:
  Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. 682-689
  
• Éric Fusy, Dominique Poulalhon, Gilles Schaeffer:
  Dissections and trees, with applications to optimal mesh encoding and to random sampling. 690-699
  
• David Gamarnik:
  The expected value of random minimal length spanning tree of a complete graph. 700-704
  
• Martin Kochol:
  Girth restrictions for the 5-flow conjecture. 705-707
  
• Noga Alon, Asaf Shapira:
  Linear equations, arithmetic progressions and hypergraph property testing. 708-717
  

Session 8B

• Joan Boyar, Lene M. Favrholdt, Kim S. Larsen:
  The relative worst order ratio applied to paging. 718-727
  
• Günter Rote:
  Strictly convex drawings of planar graphs. 728-734
  
• Rezaul Alam Chowdhury, Vijaya Ramachandran:
  External-memory exact and approximate all-pairs shortest-paths in undirected graphs. 735-744
  
• Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang:
  Graph distances in the streaming model: the value of space. 745-754
  
• Jeff Erickson:
  Lower bounds for external algebraic decision trees. 755-761
  

Session 8C

• Hubert T.-H. Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou:
  On hierarchical routing in doubling metrics. 762-771
  
• Eyal Even-Dar, Yishay Mansour:
  Fast convergence of selfish rerouting. 772-781
  
• Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke:
  Oblivious routing on node-capacitated and directed graphs. 782-790
  
• Harald Räcke, Adi Rosén:
  Distributed online call control on general networks. 791-800
  
• Fei Li, Jay Sethuraman, Clifford Stein:
  An optimal online algorithm for packet scheduling with agreeable deadlines. 801-802
  

Session 9A

• Pankaj K. Agarwal, Lars Arge, Ke Yi:
  An optimal dynamic interval stabbing-max data structure? 803-812
  
• Robert Endre Tarjan, Renato Fonseca F. Werneck:
  Self-adjusting top trees. 813-822
  
• Anna Pagh, Rasmus Pagh, S. Srinivasa Rao:
  An optimal Bloom filter replacement. 823-829
  
• Rina Panigrahy:
  Efficient hashing with lookups in two memory accesses. 830-839
  
• A. Robert Calderbank, Anna C. Gilbert, Kirill Levchenko, S. Muthukrishnan, Martin Strauss:
  Improved range-summable random variable construction algorithms. 840-849
  

Session 9B

• Amin Coja-Oghlan:
  A spectral heuristic for bisecting random graphs. 850-859
  
• Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian:
  Complete partitions of graphs. 860-869
  
• Tomás Feder, Pavol Hell, Daniel Král, Jiri Sgall:
  Two algorithms for general list matrix partitions. 870-876
  
• Sariel Har-Peled, Bardia Sadri:
  How fast is the k-means method? 877-885
  
• Boris Aronov, Sariel Har-Peled:
  On approximating the depth and related problems. 886-894
  

Session 9C

• Yuichiro Miyamoto, Tomomi Matsui:
  Multicoloring unit disk graphs on triangular lattice points. 895-896
  
• Peter Sanders, David Steurer:
  An asymptotic approximation scheme for multigraph edge coloring. 897-906
  
• Pinar Heggernes, Jan Arne Telle, Yngve Villanger:
  Computing minimal triangulations in time O(n^alpha log n) = o(n^2.376). 907-916
  
• Timothy M. Chan:
  Finding the shortest bottleneck edge in a parametric minimum spanning tree. 917-918
  
• Abraham D. Flaxman, Alan M. Frieze, Michael Krivelevich:
  On the random 2-stage minimum spanning tree. 919-926
  

Invited Plenary Abstract

• Uriel Feige:
  Rigorous analysis of heuristics for NP-hard problems. 927
  

Session 11A

• Friedrich Eisenbrand, Fabrizio Grandoni:
  An improved approximation algorithm for virtual private network design. 928-932
  
• Ara Hayrapetyan, Chaitanya Swamy, Éva Tardos:
  Network design for information networks. 933-942
  
• Julia Chuzhoy, Anupam Gupta, Joseph Naor, Amitabh Sinha:
  On the approximability of some network design problems. 943-951
  
• Julia Chuzhoy, Yuval Rabani:
  Approximating k-median with non-uniform capacities. 952-958
  
• Naveen Garg, Rohit Khandekar, Vinayaka Pandit:
  Improved approximation for universal facility location. 959-960
  

Session 11B

• Colin Cooper, Alan M. Frieze:
  The cover time of two classes of random graphs. 961-970
  
• Thomas P. Hayes, Eric Vigoda:
  Coupling with the stationary distribution and improved sampling for colorings and independent sets. 971-979
  
• Colin Cooper, Martin E. Dyer, Catherine S. Greenhill:
  Sampling regular graphs and a peer-to-peer network. 980-988
  
• S. Muthukrishnan, Gopal Pandurangan:
  The bin-covering technique for thresholding random geometric graph properties. 989-998
  
• Stefanie Gerke, Colin McDiarmid, Angelika Steger, Andreas Weißl:
  Random planar graphs with n nodes and a fixed number of edges. 999-1007
  

Session 11C

• Ravi Krishna Kolluri:
  Provably good moving least squares. 1008-1017
  
• Siu-Wing Cheng, Tamal K. Dey, Edgar A. Ramos:
  Manifold reconstruction from point samples. 1018-1027
  
• Tamal K. Dey, Joachim Giesen, Samrat Goswami:
  Delaunay triangulations approximate anchor hulls. 1028-1037
  
• Jeff Erickson, Kim Whittlesey:
  Greedy optimal homotopy and homology generators. 1038-1046
  
• Stefan Funke, Christian Klein, Kurt Mehlhorn, Susanne Schmitt:
  Controlled perturbation for Delaunay triangulations. 1047-1056
  

Session 12A

• László Babai, Thomas P. Hayes:
  Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. 1057-1066
  
• Benjamin Doerr:
  Matrix rounding with low error in small submatrices. 1067-1068
  
• Victor Y. Pan:
  Can the TPRI structure help us to solve the algebraic eigenproblem? 1069-1078
  
• Sung-il Pae, Michael C. Loui:
  Optimal random number generation from a biased coin. 1079-1088
  
• Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright:
  A new look at survey propagation and its generalizations. 1089-1098
  

Session 12B

• Andris Ambainis, Julia Kempe, Alexander Rivosh:
  Coins make quantum walks faster. 1099-1108
  
• Frédéric Magniez, Miklos Santha, Mario Szegedy:
  Quantum algorithms for the triangle problem. 1109-1117
  
• Julia Kempe, Aner Shalev:
  The hidden subgroup problem and permutation group theory. 1118-1125
  
• Damon Mosk-Aoyama, Mihalis Yannakakis:
  Testing hierarchical systems. 1126-1135
  
• Viraj Kumar, Mahesh Viswanathan:
  Conformance testing in the presence of multiple faults. 1136-1145
  

Session 12C

• Ron Lavi, Noam Nisan:
  Online ascending auctions for gradually expiring items. 1146-1155
  
• Avrim Blum, Jason D. Hartline:
  Near-optimal online auctions. 1156-1163
  
• Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry:
  On profit-maximizing envy-free pricing. 1164-1173
  
• Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Mark R. Tuttle:
  Improved recommendation systems. 1174-1183
  
• Tim Roughgarden:
  Selfish routing with atomic players. 1184-1185