19. SODA 2008:
San Francisco,
California,
USA
Shang-Hua Teng (Ed.):
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008.
SIAM 2008
- 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 lN1 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 Sn.
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
Copyright © Sat Nov 7 03:09:58 2009
by Michael Ley (ley@uni-trier.de)