default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID16th SODA 2005: Vancouver, BC, Canada
- Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005. SIAM 2005, ISBN 0-89871-585-7
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 Henriques 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 Tsz-Hong 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, Jirí 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(nalpha log n) = o(n2.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
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-12-05 22:31 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:
