19. SODA 2008: San Francisco, California, USA

• Nir Ailon, Edo Liberty:
  Fast dimension reduction using Rademacher series on dual BCH codes. 1-9
  
• Ping Li:
  Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections. 10-19
  
• Mark A. Iwen:
  A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods. 20-29
  
• Piotr Indyk:
  Explicit constructions for compressed sensing of sparse signals. 30-33
  
• Aaron Bernstein, David R. Karger:
  Improved distance sensitivity oracles via random sampling. 34-43
  
• S. Thomas McCormick, Satoru Fujishige:
  Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. 44-53
  
• Jin-yi Cai, Pinyan Lu:
  Holographic algorithms with unsymmetric signatures. 54-63
  
• Guy Kindler, Assaf Naor, Gideon Schechtman:
  The UGC hardness threshold of the ℓ_p Grothendieck problem. 64-73
  
• Ilias Diakonikolas, Mihalis Yannakakis:
  Succinct approximate convex pareto curves. 74-83
  
• Daniele Micciancio:
  Efficient reductions among lattice problems. 84-93
  
• Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos:
  Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. 94-101
  
• Raghavan Dhandapani:
  Greedy drawings of triangulations. 102-111
  
• Siu-Wing Cheng, Tamal K. Dey:
  Maintaining deforming surface meshes. 112-121
  
• Arno Eigenwillig, Michael Kerber:
  Exact and efficient 2D-arrangements of arbitrary algebraic curves. 122-131
  
• Nicla Bernasconi, Konstantinos Panagiotou, Angelika Steger:
  On properties of random dissections and triangulations. 132-141
  
• Bonnie Berger, Rohit Singh, Jinbo Xu:
  Graph algorithms for biological systems analysis. 142-151
  
• Julián Mestre:
  Adaptive local ratio. 152-160
  
• Ulrich Faigle, Britta Peis:
  Two-phase greedy algorithms for some classes of combinatorial linear programs. 161-166
  
• Ding-Zhu Du, Ronald L. Graham, Panos M. Pardalos, Peng-Jun Wan, Weili Wu, Wenbo Zhao:
  Analysis of greedy approximations with nonsubmodular potential functions. 167-175
  
• Claire Mathieu, Warren Schudy:
  Yet another algorithm for dense max cut: go greedy. 176-182
  
• Ignaz Rutter, Alexander Wolff:
  Computing large matchings fast. 183-192
  
• Penny E. Haxell, Gordon T. Wilfong:
  A fractional model of the border gateway protocol (BGP). 193-199
  
• Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan:
  Minimizing average latency in oblivious routing. 200-207
  
• Gianluca De Marco:
  Distributed broadcast in unknown radio networks. 208-217
  
• Robert Elsässer, Thomas Sauerwald:
  The power of memory in randomized broadcasting. 218-227
  
• Amos Fiat, Yishay Mansour, Uri Nadav:
  Competitive queue management for latency sensitive packets. 228-237
  
• Elchanan Mossel, Allan Sly:
  Rapid mixing of Gibbs sampling on graphs that are sparse on average. 238-247
  
• László Babai, Nikolay Nikolov, László Pyber:
  Product growth and mixing in finite groups. 248-257
  
• Venkatesan Guruswami, Atri Rudra:
  Concatenated codes can achieve list-decoding capacity. 258-267
  
• Mark Braverman, Elchanan Mossel:
  Noisy sorting without resampling. 268-276
  
• Michael Zuckerman, Ariel D. Procaccia, Jeffrey S. Rosenschein:
  Algorithms for the coalitional manipulation problem. 277-286
  
• Uriel Feige:
  On allocations that maximize fairness. 287-293
  
• Susanne Albers:
  On the value of coordination in network design. 294-303
  
• Matthew Cary, Abraham D. Flaxman, Jason D. Hartline, Anna R. Karlin:
  Auctions for structured procurement. 304-313
  
• Baruch Awerbuch, Yossi Azar, Rohit Khandekar:
  Fast load balancing via bounded best response. 314-322
  
• Yossi Azar, Kamal Jain, Vahab S. Mirrokni:
  (Almost) optimal coordination mechanisms for unrelated machine scheduling. 323-332
  
• T.-H. Hubert Chan, Anupam Gupta, Kunal Talwar:
  Ultra-low-dimensional embeddings for doubling metrics. 333-342
  
• Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
  Earth mover distance over high-dimensional spaces. 343-352
  
• Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
  Almost Euclidean subspaces of l^N₁ via expander codes. 353-362
  
• Ittai Abraham, Yair Bartal, Ofer Neiman:
  Embedding metric spaces in their intrinsic dimension. 363-372
  
• Noga Alon, Michael R. Capalbo:
  Optimal universal graphs with deterministic embedding. 373-378
  
• Ilan Gronau, Shlomo Moran, Sagi Snir:
  Fast and reliable reconstruction of phylogenetic trees with very short edges. 379-388
  
• Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, Udi Wieder:
  Trace reconstruction with constant deletion probability and related results. 389-398
  
• Krishnamurthy Viswanathan, Ram Swaminathan:
  Improved string reconstruction over insertion-deletion channels. 399-408
  
• Ho-Lin Chen, Ashish Goel, Chris Luhrs:
  Dimension augmentation and combinatorial criteria for efficient error-resistant DNA self-assembly. 409-418
  
• Ely Porat, Klim Efremenko:
  Approximating general metric distances between a pattern and a text. 419-427
  
• Yuval Emek, David Peleg, Liam Roditty:
  A near-linear time algorithm for computing replacement paths in planar directed graphs. 428-435
  
• Ran Duan, Seth Pettie:
  Bounded-leg distance and reachability oracles. 436-445
  
• Ken-ichi Kawarabayashi, Bruce A. Reed:
  A nearly linear time algorithm for the half integral disjoint paths packing. 446-454
  
• Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi:
  Fast edge splitting and Edmonds' arborescence construction for unweighted graphs. 455-464
  
• Virginia Vassilevska:
  Nondecreasing paths in a weighted graph or: how to optimally read a train schedule. 465-472
  
• Jessica Chang, Thomas Erlebach, Renars Gailis, Samir Khuller:
  Broadcast scheduling: algorithms and complexity. 473-482
  
• Tomás Ebenlendr, Marek Krcal, Jiri Sgall:
  Graph balancing: a special case of scheduling unrelated parallel machines. 483-490
  
• Julien Robert, Nicolas Schabanel:
  Non-clairvoyant scheduling with precedence constraints. 491-500
  
• Guy E. Blelloch, Rezaul Alam Chowdhury, Phillip B. Gibbons, Vijaya Ramachandran, Shimin Chen, Michael Kozuch:
  Provably good multicore cache performance for divide-and-conquer algorithms. 501-510
  
• Brighten Godfrey:
  Balls and bins with structure: balanced allocations on hypergraphs. 511-517
  
• Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa:
  Arc-disjoint in-trees in directed graphs. 518-526
  
• Sergio Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar:
  Finding one tight cycle. 527-531
  
• Chandra Chekuri, Guy Even, Anupam Gupta, Danny Segev:
  Set connectivity problems in undirected graphs and the directed Steiner network problem. 532-541
  
• Nicholas J. A. Harvey:
  Matroid intersection, pointer chasing, and Young's seminormal representation of S_n. 542-549
  
• Harold N. Gabow, Suzanne Gallagher:
  Iterated rounding algorithms for the smallest k-edge connected spanning subgraph. 550-559
  
• Persi Diaconis:
  Shuffling cards, adding numbers, and symmetric functions. 560
  
• Timothy M. Chan:
  On the bichromatic k-set problem. 561-570
  
• Jie Gao, Leonidas J. Guibas, Steve Oudot, Yue Wang:
  Geodesic Delaunay triangulation and witness complex in the plane. 571-580
  
• Adrian Dumitrescu, Csaba D. Tóth:
  Minimum weight convex Steiner partitions. 581-590
  
• Lee-Ad Gottlieb, Liam Roditty:
  Improved algorithms for fully dynamic geometric spanners and geometric routing. 591-600
  
• Josep Díaz, Dieter Mitsche, Xavier Pérez-Giménez:
  On the connectivity of dynamic random geometric graphs. 601-610
  
• Aravind Srinivasan:
  Improved algorithmic versions of the Lovász Local Lemma. 611-620
  
• Frédéric Havet, Bruce A. Reed, Jean-Sébastien Sereni:
  L(2, 1)-labelling of graphs. 621-630
  
• Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos:
  Catalan structures and dynamic programming in H-minor-free graphs. 631-640
  
• Isolde Adler, Martin Grohe, Stephan Kreutzer:
  Computing excluded minors. 641-650
  
• Reid Andersen, Kevin J. Lang:
  An algorithm for improving graph partitions. 651-660
  
• Chandra Chekuri, Nitish Korula, Martin Pál:
  Improved algorithms for orienteering and related problems. 661-670
  
• Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy:
  Approximation algorithms for labeling hierarchical taxonomies. 671-680
  
• Mark Huber, Jenny Law:
  Fast approximation of the permanent for very dense problems. 681-689
  
• T.-H. Hubert Chan, Anupam Gupta:
  Approximating TSP on metrics with bounded global growth. 690-699
  
• Nir Halman, Diego Klabjan, Chung-Lun Li, James B. Orlin, David Simchi-Levi:
  Fully polynomial time approximation schemes for stochastic dynamic programs. 700-709
  
• Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, Zoya Svitkina:
  On distributing symmetric streaming computations. 710-719
  
• Amit Chakrabarti, T. S. Jayram, Mihai Patrascu:
  Tight lower bounds for selection in randomly ordered streams. 720-729
  
• Funda Ergün, Hossein Jowhari:
  On distance to monotonicity and longest increasing subsequence of a data stream. 730-736
  
• Piotr Indyk, Andrew McGregor:
  Declaring independence via the sketching of sketches. 737-745
  
• Michael Mitzenmacher, Salil P. Vadhan:
  Why simple hash functions work: exploiting the entropy in a data stream. 746-755
  
• Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick:
  Maximum overhang. 756-765
  
• Joshua N. Cooper, Benjamin Doerr, Tobias Friedrich, Joel Spencer:
  Deterministic random walks on regular trees. 766-772
  
• Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald:
  Quasirandom rumor spreading. 773-781
  
• Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski:
  Universality of random graphs. 782-788
  
• Asaf Shapira, Raphael Yuster:
  The effect of induced subgraphs on quasi-randomness. 789-798
  
• Marcel R. Ackermann, Johannes Blömer, Christian Sohler:
  Clustering for metric and non-metric distance measures. 799-808
  
• Robert Krauthgamer, Tim Roughgarden:
  Metric clustering via consistent labeling. 809-818
  
• Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, Kasturi R. Varadarajan:
  On clustering to minimize the sum of radii. 819-825
  
• Ke Chen:
  A constant factor approximation algorithm for k-median clustering with outliers. 826-835
  
• Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote:
  Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension. 836-843
  
• Alex Fabrikant, Christos H. Papadimitriou:
  The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. 844-853
  
• Ho-Lin Chen, Tim Roughgarden, Gregory Valiant:
  Designing networks with good equilibria. 854-863
  
• Sushil Bikhchandani, Sven de Vries, James Schummer, Rakesh V. Vohra:
  Ascending auctions for integral (poly)matroids with concave nondecreasing separable values. 864-873
  
• Peter Bro Miltersen, Troels Bjerre Sørensen:
  Fast algorithms for finding proper strategies in game trees. 874-883
  
• Ofer Dekel, Felix A. Fischer, Ariel D. Procaccia:
  Incentive compatible regression learning. 884-893
  
• Guy E. Blelloch:
  Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. 894-903
  
• Timothy M. Chan, Eric Y. Chen:
  In-place 2-d nearest neighbor search. 904-911
  
• Sébastien Collette, Vida Dujmovic, John Iacono, Stefan Langerman, Pat Morin:
  Distribution-sensitive point location in convex subdivisions. 912-921
  
• Kenneth L. Clarkson:
  Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. 922-931
  
• Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney:
  Sampling algorithms and coresets for ℓ_p regression. 932-941
  
• Naveen Garg, Anupam Gupta, Stefano Leonardi, Piotr Sankowski:
  Stochastic analyses for online combinatorial optimization problems. 942-951
  
• Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, Maxim Sviridenko:
  Online make-to-order joint replenishment model: primal dual competitive algorithms. 952-961
  
• Michael E. Saks, C. Seshadhri:
  Parallel monotonicity reconstruction. 962-971
  
• Ioannis Caragiannis:
  Better bounds for online load balancing on unrelated machines. 972-981
  
• Gagan Goel, Aranyak Mehta:
  Online budgeted matching in random input models with applications to Adwords. 982-991
  
• Andrei Z. Broder:
  Computational advertising. 992
  
• Henry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou:
  Linked decompositions of networks and the power of choice in Polya urns. 993-1002
  
• Reid Andersen:
  A local algorithm for finding dense subgraphs. 1003-1009
  
• Prasad Chebolu, Páll Melsted:
  PageRank and the random surfer model. 1010-1018
  
• Arpita Ghosh, Mohammad Mahdian:
  Charity auctions on social networks. 1019-1028
  
• Ning Chen:
  On the approximability of influence in social networks. 1029-1037
  
• Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani:
  Fast asynchronous byzantine agreement and leader election with full information. 1038-1047
  
• Bhavani Shankar, Prasant Gopal, Kannan Srinathan, C. Pandu Rangan:
  Unconditionally reliable message transmission in directed networks. 1048-1055
  
• Chinmoy Dutta, Yashodhan Kanoria, D. Manjunath, Jaikumar Radhakrishnan:
  A tight lower bound for parity in noisy communication networks. 1056-1065
  
• James Aspnes, Muli Safra, Yitong Yin:
  Ranged hash functions and the price of churn. 1066-1075
  
• Graham Cormode, S. Muthukrishnan, Ke Yi:
  Algorithms for distributed functional monitoring. 1076-1085
  
• Amihood Amir, Igor Nor:
  Real-time indexing over fixed finite alphabets. 1086-1095
  
• Shay Mozes, Krzysztof Onak, Oren Weimann:
  Finding an optimal tree searching strategy in linear time. 1096-1105
  
• Prosenjit Bose, Karim Douïeb, Stefan Langerman:
  Dynamic optimality for skip lists and B-trees. 1106-1114
  
• Seth Pettie:
  Splay trees, Davenport-Schinzel sequences, and the deque conjecture. 1115-1124
  
• Surender Baswana, Soumojit Sarkar:
  Fully dynamic algorithm for graph spanners with poly-logarithmic update time. 1125-1134
  
• Mario Mense, Christian Scheideler:
  SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems. 1135-1144
  
• Ashish Goel, Hamid Nazerzadeh:
  Price based protocols for fair resource allocation: convergence time analysis and extension to Leontief utilities. 1145-1153
  
• Zoya Svitkina:
  Lower-bounded facility location. 1154-1163
  
• Barbara M. Anthony, Vineet Goyal, Anupam Gupta, Viswanath Nagarajan:
  A plant location guide for the unsure. 1164-1173
  
• Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, Guido Schäfer:
  Approximating connected facility location problems via random facility sampling and core detouring. 1174-1183
  
• Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii:
  The hiring problem and Lake Wobegon strategies. 1184-1193
  
• Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky:
  Weak ε-nets and interval chains. 1194-1203
  
• Takuro Fukunaga, Magnús M. Halldórsson, Hiroshi Nagamochi:
  Robust cost colorings. 1204-1212
  
• Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron:
  Comparing the strength of query types in property testing: the case of testing k-colorability. 1213-1222
  
• Nayantara Bhatnagar, Sam Greenberg, Dana Randall:
  Sampling stable marriages: why spouse-swapping won't work. 1223-1232
  
• Adrian Dumitrescu, Csaba D. Tóth:
  On stars and Steiner stars. 1233-1240
  
• Boris Aronov, Mark de Berg, Chris Gray, Elena Mumford:
  Cutting cycles of rods in space: hardness and approximation. 1241-1248
  
• Olivier Devillers, Jeff Erickson, Xavier Goaoc:
  Empty-ellipse graphs. 1249-1257
  
• David Eppstein:
  Recognizing partial cubes in quadratic time. 1258-1266
  
• Thomas Erlebach, Erik Jan van Leeuwen:
  Approximating geometric coverage problems. 1267-1276