16. 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 BibTeX
Session 1A
Session 1B
- James Aspnes, Kevin L. Chang, Aleksandr Yampolskiy:
Inoculation strategies for victims of viruses and the sum-of-squares partition problem.
43-52
Electronic Edition (ACM DL) BibTeX
- Nicole Immorlica, Mohammad Mahdian:
Marriage, honesty, and stability.
53-62
Electronic Edition (ACM DL) BibTeX
- Kamal Jain, Vijay V. Vazirani, Yinyu Ye:
Market equilibria for homothetic, quasi-concave utilities and economies of scale in production.
63-71
Electronic Edition (ACM DL) BibTeX
- Bruno Codenotti, Sriram V. Pemmaraju, Kasturi R. Varadarajan:
On the polynomial time computation of equilibria for certain exchange economies.
72-81
Electronic Edition (ACM DL) BibTeX
- Christos H. Papadimitriou, Tim Roughgarden:
Computing equilibria in multi-player games.
82-91
Electronic Edition (ACM DL) BibTeX
Session 1C
- James R. Lee:
On distance scales, embeddings, and efficient relaxations of the cut cone.
92-101
Electronic Edition (ACM DL) BibTeX
- Shuchi Chawla, Anupam Gupta, Harald Räcke:
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.
102-111
Electronic Edition (ACM DL) BibTeX
- Christos H. Papadimitriou, Shmuel Safra:
The complexity of low-distortion embeddings between point sets.
112-118
Electronic Edition (ACM DL) BibTeX
- 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
Electronic Edition (ACM DL) BibTeX
- Moses Charikar, Adriana Karagiozova:
A tight threshold for metric Ramsey phenomena.
129-136
Electronic Edition (ACM DL) BibTeX
Invited Plenary Abstract
Session 3A
Session 3B
- Andrei Z. Broder, Michael Mitzenmacher:
Multidimensional balanced allocations.
195-196
Electronic Edition (ACM DL) BibTeX
- Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton:
Online client-server load balancing without global information.
197-206
Electronic Edition (ACM DL) BibTeX
- Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko:
Job shop scheduling with unit processing times.
207-214
Electronic Edition (ACM DL) BibTeX
- Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor:
Approximating the average response time in broadcast scheduling.
215-221
Electronic Edition (ACM DL) BibTeX
- Michael Elkin, Guy Kortsarz:
Improved schedule for radio broadcast.
222-231
Electronic Edition (ACM DL) BibTeX
Session 3C
Session 4A
Session 4B
Session 4C
- Retsef Levi, Robin Roundy, David B. Shmoys:
A constant approximation algorithm for the one-warehouse multi-retailer problem.
365-374
Electronic Edition (ACM DL) BibTeX
- Luca Becchetti, Jochen Könemann, Stefano Leonardi, Martin Pál:
Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy.
375-384
Electronic Edition (ACM DL) BibTeX
- Abraham Flaxman, Adam Tauman Kalai, H. Brendan McMahan:
Online convex optimization in the bandit setting: gradient descent without a gradient.
385-394
Electronic Edition (ACM DL) BibTeX
- Brian C. Dean, Michel X. Goemans, Jan Vondrák:
Adaptivity and approximation for stochastic packing problems.
395-404
Electronic Edition (ACM DL) BibTeX
- Anthony Man-Cho So, Yinyu Ye:
Theory of semidefinite programming for sensor network localization.
405-414
Electronic Edition (ACM DL) BibTeX
Session 5A
Session 5B
Session 5C
- Vladlen Koltun:
Pianos are not flat: rigid motion planning in three dimensions.
505-514
Electronic Edition (ACM DL) BibTeX
- Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell:
A constant-factor approximation algorithm for optimal terrain guarding.
515-524
Electronic Edition (ACM DL) BibTeX
- Micha Sharir, Hayim Shaul:
Ray shooting amid balls, farthest point from a line, and range emptiness searching.
525-534
Electronic Edition (ACM DL) BibTeX
- Sunil Arya, Theocharis Malamatos, David M. Mount:
Space-time tradeoffs for approximate spherical range counting.
535-544
Electronic Edition (ACM DL) BibTeX
- 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
Electronic Edition (ACM DL) BibTeX
Invited Plenary Abstract
Session 7A
Session 7B
Session 7C
- Aleksandrs Slivkins:
Distributed approaches to triangulation and embedding.
640-649
Electronic Edition (ACM DL) BibTeX
- 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
Electronic Edition (ACM DL) BibTeX
- Don Coppersmith, Michael Elkin:
Sparse source-wise and pair-wise distance preservers.
660-669
Electronic Edition (ACM DL) BibTeX
- Pankaj K. Agarwal, Yusu Wang, Peng Yin:
Lower bound for sparse Euclidean spanners.
670-671
Electronic Edition (ACM DL) BibTeX
- Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie:
New constructions of (alpha, beta)-spanners and purely additive spanners.
672-681
Electronic Edition (ACM DL) BibTeX
Session 8A
Session 8B
Session 8C
- Hubert T.-H. Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou:
On hierarchical routing in doubling metrics.
762-771
Electronic Edition (ACM DL) BibTeX
- Eyal Even-Dar, Yishay Mansour:
Fast convergence of selfish rerouting.
772-781
Electronic Edition (ACM DL) BibTeX
- Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke:
Oblivious routing on node-capacitated and directed graphs.
782-790
Electronic Edition (ACM DL) BibTeX
- Harald Räcke, Adi Rosén:
Distributed online call control on general networks.
791-800
Electronic Edition (ACM DL) BibTeX
- Fei Li, Jay Sethuraman, Clifford Stein:
An optimal online algorithm for packet scheduling with agreeable deadlines.
801-802
Electronic Edition (ACM DL) BibTeX
Session 9A
Session 9B
Session 9C
Invited Plenary Abstract
Session 11A
Session 11B
Session 11C
Session 12A
Session 12B
Session 12C
- Ron Lavi, Noam Nisan:
Online ascending auctions for gradually expiring items.
1146-1155
Electronic Edition (ACM DL) BibTeX
- Avrim Blum, Jason D. Hartline:
Near-optimal online auctions.
1156-1163
Electronic Edition (ACM DL) BibTeX
- Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry:
On profit-maximizing envy-free pricing.
1164-1173
Electronic Edition (ACM DL) BibTeX
- Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Mark R. Tuttle:
Improved recommendation systems.
1174-1183
Electronic Edition (ACM DL) BibTeX
- Tim Roughgarden:
Selfish routing with atomic players.
1184-1185
Electronic Edition (ACM DL) BibTeX
Copyright © Sat May 16 23:41:53 2009
by Michael Ley (ley@uni-trier.de)
