20. SODA 2009:
New York,
NY,
USA
Claire Mathieu (Ed.):
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009.
SIAM 2009 BibTeX
- Gabriel Nivasch:
Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations.
1-10
Electronic Edition (ACM DL) BibTeX
- Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect matchings via uniform sampling in regular bipartite graphs.
11-17
Electronic Edition (ACM DL) BibTeX
- Ashish Goel, Sanjeev Khanna, Brad Null:
The ratio index for budgeted learning, with applications.
18-27
Electronic Edition (ACM DL) BibTeX
- Sudipto Guha, Kamesh Munagala, Peng Shi:
Approximation algorithms for restless bandit problems.
28-37
Electronic Edition (ACM DL) BibTeX
- Elad Hazan, Satyen Kale:
Better algorithms for benign bandits.
38-47
Electronic Edition (ACM DL) BibTeX
- Colin Cooper, Alan M. Frieze:
The cover time of random geometric graphs.
48-57
Electronic Edition (ACM DL) BibTeX
- Ilia Binder, Mark Braverman:
The complexity of simulating Brownian Motion.
58-67
Electronic Edition (ACM DL) BibTeX
- Sergi Elizalde, Peter Winkler:
Sorting by placement and shift.
68-75
Electronic Edition (ACM DL) BibTeX
- Sam Greenberg, Amanda Pascoe, Dana Randall:
Sampling biased lattice configurations using exponential metrics.
76-85
Electronic Edition (ACM DL) BibTeX
- Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha:
On the hitting times of quantum versus random walks.
86-95
Electronic Edition (ACM DL) BibTeX
- Alon Shalita, Uri Zwick:
Efficient algorithms for the 2-gathering problem.
96-105
Electronic Edition (ACM DL) BibTeX
- Michael Molloy, Bruce A. Reed:
Asymptotically optimal frugal colouring.
106-114
Electronic Edition (ACM DL) BibTeX
- Stéphan Thomassé, Stéphan Thomassé:
A quadratic kernel for feedback vertex set.
115-119
Electronic Edition (ACM DL) BibTeX
- Zdenek Dvorak, Daniel Král, Robin Thomas:
Coloring triangle-free graphs on surfaces.
120-129
Electronic Edition (ACM DL) BibTeX
- Michael Drmota, Wojciech Szpankowski:
(Un)expected behavior of digital search tree profile.
130-138
Electronic Edition (ACM DL) BibTeX
- Michael I. Jordan:
Combinatorial stochastic processes and nonparametric Bayesian modeling.
139
Electronic Edition (ACM DL) BibTeX
- Timothy M. Chan:
Comparison-based time-space lower bounds for selection.
140-149
Electronic Edition (ACM DL) BibTeX
- David Eppstein, Michael T. Goodrich, Darren Strash:
Linear-time algorithms for geometric graphs with sublinearly many crossings.
150-159
Electronic Edition (ACM DL) BibTeX
- David Eppstein, Elena Mumford:
Self-overlapping curves revisited.
160-169
Electronic Edition (ACM DL) BibTeX
- Haim Kaplan, Natan Rubin, Micha Sharir:
Line transversals of convex polyhedra in R3.
170-179
Electronic Edition (ACM DL) BibTeX
- Peyman Afshani, Timothy M. Chan:
Optimal halfspace range reporting in three dimensions.
180-186
Electronic Edition (ACM DL) BibTeX
- J. Salez, D. Shah:
Optimality of belief propagation for random assignment problem.
187-196
Electronic Edition (ACM DL) BibTeX
- Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger:
Termination criteria for solving concurrent safety and reachability games.
197-206
Electronic Edition (ACM DL) BibTeX
- Amin Coja-Oghlan, Colin Cooper, Alan M. Frieze:
An efficient sparse regularity concept.
207-216
Electronic Edition (ACM DL) BibTeX
- Yury Person, Mathias Schacht:
Almost all hypergraphs without Fano planes are bipartite.
217-226
Electronic Edition (ACM DL) BibTeX
- Brendan Nagle, Annika Poerschke, Vojtech Rödl, Mathias Schacht:
Hypergraph regularity and quasi-randomness.
227-235
Electronic Edition (ACM DL) BibTeX
- Philip Klein, Shay Mozes, Oren Weimann:
Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2 n)-time algorithm.
236-245
Electronic Edition (ACM DL) BibTeX
- David R. Karger, Debmalya Panigrahi:
A near-linear time algorithm for constructing a cactus representation of minimum cuts.
246-255
Electronic Edition (ACM DL) BibTeX
- Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing halfspaces.
256-264
Electronic Edition (ACM DL) BibTeX
- Anand Bhalgat, Ramesh Hariharan:
Fast edge orientation for unweighted graphs.
265-272
Electronic Edition (ACM DL) BibTeX
- Omid Amini, Louis Esperet, Jan van den Heuvel:
A unified approach to distance-two colouring of planar graphs.
273-282
Electronic Edition (ACM DL) BibTeX
- Pankaj K. Agarwal, R. Sharathkumar, Hai Yu:
Approximate Euclidean shortest paths amid convex obstacles.
283-292
Electronic Edition (ACM DL) BibTeX
- Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen:
Approximate line nearest neighbor in high dimensions.
293-301
Electronic Edition (ACM DL) BibTeX
- Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David Orden, Pedro Ramos:
Decomposition of multiple coverings into more parts.
302-310
Electronic Edition (ACM DL) BibTeX
- Adrian Dumitrescu, Csaba D. Tóth, Guangwu Xu:
On stars and Steiner stars: II.
311-317
Electronic Edition (ACM DL) BibTeX
- Yury Lifshits, Shengyu Zhang:
Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design.
318-326
Electronic Edition (ACM DL) BibTeX
- Edith Elkind, Dmitrii V. Pasechnik:
Computing the nucleolus of weighted voting games.
327-335
Electronic Edition (ACM DL) BibTeX
- Ehsan Amiri, Gábor Tardos:
High rate fingerprinting codes and the fingerprinting capacity.
336-345
Electronic Edition (ACM DL) BibTeX
- Noga Alon, Uriel Feige:
On the power of two, three and four probes.
346-354
Electronic Edition (ACM DL) BibTeX
- Toniann Pitassi, Nathan Segerlind:
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.
355-364
Electronic Edition (ACM DL) BibTeX
- Ryan O'Donnell, Yi Wu:
3-bit dictator testing: 1 vs. 5/8.
365-373
Electronic Edition (ACM DL) BibTeX
- Markus Chimani, Carsten Gutwenger, Petra Mutzel, Christian Wolf:
Inserting a vertex into a planar graph.
375-383
Electronic Edition (ACM DL) BibTeX
- Ran Duan, Seth Pettie:
Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths.
384-391
Electronic Edition (ACM DL) BibTeX
- Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin:
Sorting and selection in posets.
392-401
Electronic Edition (ACM DL) BibTeX
- Parikshit Gopalan, Jaikumar Radhakrishnan:
Finding duplicates in a data stream.
402-411
Electronic Edition (ACM DL) BibTeX
- Ping Li:
Compressed counting.
412-421
Electronic Edition (ACM DL) BibTeX
- Bernard Chazelle:
Natural algorithms.
422-431
Electronic Edition (ACM DL) BibTeX
- Konstantinos Panagiotou, Angelika Steger:
Maximal biconnected subgraphs of random planar graphs.
432-440
Electronic Edition (ACM DL) BibTeX
- James Aspnes, Keren Censor:
Approximate shared-memory counting despite a strong adversary.
441-450
Electronic Edition (ACM DL) BibTeX
- Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik:
On smoothed k-CNF formulas and the Walksat algorithm.
451-460
Electronic Edition (ACM DL) BibTeX
- Bodo Manthey, Heiko Röglin:
Improved smoothed analysis of the k-means method.
461-470
Electronic Edition (ACM DL) BibTeX
- Amr Elmasry:
Pairing heaps with O(log log n) decrease cost.
471-476
Electronic Edition (ACM DL) BibTeX
- Haim Kaplan, Uri Zwick:
A simpler implementation and analysis of Chazelle's soft heaps.
477-485
Electronic Edition (ACM DL) BibTeX
- Vida Dujmovic, John Howat, Pat Morin:
Biased range trees.
486-495
Electronic Edition (ACM DL) BibTeX
- Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu:
The geometry of binary search trees.
496-505
Electronic Edition (ACM DL) BibTeX
- Ran Duan, Seth Pettie:
Dual-failure distance and connectivity oracles.
506-515
Electronic Edition (ACM DL) BibTeX
- Viswanath Nagarajan, Maxim Sviridenko:
On the maximum quadratic assignment problem.
516-524
Electronic Edition (ACM DL) BibTeX
- Prasad Raghavendra, David Steurer:
Towards computing the Grothendieck constant.
525-534
Electronic Edition (ACM DL) BibTeX
- Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni:
Approximating submodular functions everywhere.
535-544
Electronic Edition (ACM DL) BibTeX
- Ariel Kulik, Hadas Shachnai, Tami Tamir:
Maximizing submodular set functions subject to multiple linear constraints.
545-554
Electronic Edition (ACM DL) BibTeX
- Aurore Amaudruz, Christina Fragouli:
Combinatorial algorithms for wireless information flow.
555-564
Electronic Edition (ACM DL) BibTeX
- Volker Strassen:
Probability, algorithms and complexity.
565
Electronic Edition (ACM DL) BibTeX
- Mohsen Bayati, Andrea Montanari, Amin Saberi:
Generating random graphs with large girth.
566-575
Electronic Edition (ACM DL) BibTeX
- Navin Goyal, Luis Rademacher, Santosh Vempala:
Expanders via random spanning trees.
576-585
Electronic Edition (ACM DL) BibTeX
- Lorenz Minder, Alistair Sinclair:
The extended k-tree algorithm.
586-595
Electronic Edition (ACM DL) BibTeX
- David Gamarnik, Dmitriy Katz:
Sequential cavity method for computing limits of the log-partition function for lattice models.
596-605
Electronic Edition (ACM DL) BibTeX
- Serge Gaspers, Gregory B. Sorkin:
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.
606-615
Electronic Edition (ACM DL) BibTeX
- Sergio Cabello:
Finding shortest contractible and shortest separating cycles in embedded graphs.
616-624
Electronic Edition (ACM DL) BibTeX
- Alexander Golynski:
Cell probe lower bounds for succinct data structures.
625-634
Electronic Edition (ACM DL) BibTeX
- Prosenjit Bose, Eric Y. Chen, Meng He, Anil Maheshwari, Pat Morin:
Succinct geometric indexes supporting point location queries.
635-644
Electronic Edition (ACM DL) BibTeX
- Kevin Buchin, Maike Buchin, Yusu Wang:
Exact algorithms for partial curve matching via the Fréchet distance.
645-654
Electronic Edition (ACM DL) BibTeX
- Mikkel Thorup:
String hashing for linear probing.
655-664
Electronic Edition (ACM DL) BibTeX
- Klaus Jansen:
Parameterized approximation scheme for the multiple knapsack problem.
665-674
Electronic Edition (ACM DL) BibTeX
- Florian Diedrich, Klaus Jansen:
Improved approximation algorithms for scheduling with fixed jobs.
675-684
Electronic Edition (ACM DL) BibTeX
- Jeff Edmonds, Kirk Pruhs:
Scalably scheduling processes with arbitrary speedup curves.
685-692
Electronic Edition (ACM DL) BibTeX
- Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs:
Speed scaling with an arbitrary power function.
693-701
Electronic Edition (ACM DL) BibTeX
- Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour:
A logarithmic approximation for unsplittable flow on line graphs.
702-709
Electronic Edition (ACM DL) BibTeX
- Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant:
On the complexity of Nash equilibria of action-graph games.
710-719
Electronic Edition (ACM DL) BibTeX
- Elad Hazan, Robert Krauthgamer:
How hard is it to approximate the best Nash equilibrium?
720-727
Electronic Edition (ACM DL) BibTeX
- Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Improved equilibria via public service advertising.
728-737
Electronic Edition (ACM DL) BibTeX
- Baharak Rastegari, Anne Condon, Kevin Leyton-Brown:
Stepwise randomized combinatorial auctions achieve revenue monotonicity.
738-747
Electronic Edition (ACM DL) BibTeX
- Umang Bhaskar, Lisa Fleischer, Darrell Hoy, Chien-Chung Huang:
Equilibria of atomic flow games are not unique.
748-757
Electronic Edition (ACM DL) BibTeX
- Mordecai Golin, Xiaoming Xu, Jiajin Yu:
A generic top-down dynamic-programming approach to prefix-free coding.
758-767
Electronic Edition (ACM DL) BibTeX
- Paolo Ferragina, Igor Nitto, Rossano Venturini:
On the bit-complexity of Lempel-Ziv compression.
768-777
Electronic Edition (ACM DL) BibTeX
- Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild:
From coding theory to efficient pattern matching.
778-784
Electronic Edition (ACM DL) BibTeX
- Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna:
Monotone minimal perfect hashing: searching a sorted table with O(1) accesses.
785-794
Electronic Edition (ACM DL) BibTeX
- Martin Dietzfelbinger, Ulf Schellbach:
On risks of using cuckoo hashing with simple universal hash classes.
795-804
Electronic Edition (ACM DL) BibTeX
- MohammadHossein Bateni, MohammadTaghi Hajiaghayi:
Assignment problem in content distribution networks: unsplittable hard-capacitated facility location.
805-814
Electronic Edition (ACM DL) BibTeX
- Ioannis Caragiannis:
Efficient coordination mechanisms for unrelated machine scheduling.
815-824
Electronic Edition (ACM DL) BibTeX
- Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
Clique-width: on the price of generality.
825-834
Electronic Edition (ACM DL) BibTeX
- Benjamin Aminof, Orna Kupferman, Robby Lampert:
Reasoning about online algorithms with weighted automata.
835-844
Electronic Edition (ACM DL) BibTeX
- Mehmet A. Begen, Maurice Queyranne:
Appointment scheduling with discrete random durations.
845-854
Electronic Edition (ACM DL) BibTeX
- Jirí Matousek, Martin Tancer, Uli Wagner:
Hardness of embedding simplicial complexes in Rd.
855-864
Electronic Edition (ACM DL) BibTeX
- Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Overcoming the l1 non-embeddability barrier: algorithms for product metrics.
865-874
Electronic Edition (ACM DL) BibTeX
- Ittai Abraham, Yair Bartal, Ofer Neiman:
On low dimensional local embeddings.
875-884
Electronic Edition (ACM DL) BibTeX
- William B. Johnson, Assaf Naor:
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite.
885-891
Electronic Edition (ACM DL) BibTeX
- Parinya Chalermsook, Julia Chuzhoy:
Maximum independent set of rectangles.
892-901
Electronic Edition (ACM DL) BibTeX
- Dániel Marx:
Approximating fractional hypertree width.
902-911
Electronic Edition (ACM DL) BibTeX
- Zeev Nutov:
An almost O(log k)-approximation for k-connected subgraphs.
912-921
Electronic Edition (ACM DL) BibTeX
- Moran Feldman, Guy Kortsarz, Zeev Nutov:
Improved approximating algorithms for Directed Steiner Forest.
922-931
Electronic Edition (ACM DL) BibTeX
- Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-closure spanners.
932-941
Electronic Edition (ACM DL) BibTeX
- Robert Krauthgamer, Joseph Naor, Roy Schwartz:
Partitioning graphs into balanced components.
942-949
Electronic Edition (ACM DL) BibTeX
- Raphael Yuster:
Efficient algorithms on sets of permutations, dominance, and real-weighted APSP.
950-957
Electronic Edition (ACM DL) BibTeX
- Omid Madani, Mikkel Thorup, Uri Zwick:
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths.
958-967
Electronic Edition (ACM DL) BibTeX
- Christos Boutsidis, Michael W. Mahoney, Petros Drineas:
An improved approximation algorithm for the column subset selection problem.
968-977
Electronic Edition (ACM DL) BibTeX
- Joel A. Tropp:
Column subset selection, matrix factorization, and eigenvalue optimization.
978-986
Electronic Edition (ACM DL) BibTeX
- Aaron Williams:
Loopless generation of multiset permutations using a constant number of variables by prefix shifts.
987-996
Electronic Edition (ACM DL) BibTeX
- Yuval Peres:
The unreasonable effectiveness of martingales.
997-1000
Electronic Edition (ACM DL) BibTeX
- Siu-Wing Cheng, Man-Kwun Chiu:
Dimension detection via slivers.
1001-1010
Electronic Edition (ACM DL) BibTeX
- David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov:
Persistent homology for kernels, images, and cokernels.
1011-1020
Electronic Edition (ACM DL) BibTeX
- Frédéric Chazal, Leonidas J. Guibas, Steve Oudot, Primoz Skraba:
Analysis of scalar fields over point cloud data.
1021-1030
Electronic Edition (ACM DL) BibTeX
- Mikhail Belkin, Jian Sun, Yusu Wang:
Constructing Laplace operator from point clouds in Rd.
1031-1040
Electronic Edition (ACM DL) BibTeX
- Benoît Hudson, Gary L. Miller, Todd Phillips, Don Sheehy:
Size complexity of volume meshes vs. surface meshes.
1041-1047
Electronic Edition (ACM DL) BibTeX
- Siddharth Barman, Shuchi Chawla:
Packing multiway cuts in capacitated graphs.
1048-1057
Electronic Edition (ACM DL) BibTeX
- Ioannis Caragiannis, Jason A. Covey, Michal Feldman, Christopher M. Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel D. Procaccia, Jeffrey S. Rosenschein:
On the approximability of Dodgson and Young elections.
1058-1067
Electronic Edition (ACM DL) BibTeX
- Maria-Florina Balcan, Avrim Blum, Anupam Gupta:
Approximate clustering without the approximation.
1068-1077
Electronic Edition (ACM DL) BibTeX
- S. Charles Brubaker:
Robust PCA and clustering in noisy mixtures.
1078-1087
Electronic Edition (ACM DL) BibTeX
- Marcel R. Ackermann, Johannes Blömer:
Coresets and approximate clustering for Bregman divergences.
1088-1097
Electronic Edition (ACM DL) BibTeX
- Ke Yi, Qin Zhang:
Multi-dimensional online tracking.
1098-1107
Electronic Edition (ACM DL) BibTeX
- Michael A. Bender, Jeremy T. Fineman, Seth Gilbert:
A new approach to incremental topological ordering.
1108-1115
Electronic Edition (ACM DL) BibTeX
- Chandra Chekuri, Benjamin Moseley:
Online scheduling to minimize the maximum delay factor.
1116-1125
Electronic Edition (ACM DL) BibTeX
- Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak:
Collecting weighted items from a dynamic queue.
1126-1135
Electronic Edition (ACM DL) BibTeX
- Spyros Angelopoulos, Pascal Schweitzer:
Paging and list update under bijective analysis.
1136-1145
Electronic Edition (ACM DL) BibTeX
- Yusuke Kobayashi, Ken-ichi Kawarabayashi:
Algorithms for finding an induced cycle in planar graphs and bounded genus graphs.
1146-1155
Electronic Edition (ACM DL) BibTeX
- Ken-ichi Kawarabayashi, Bojan Mohar:
List-color-critical graphs on a fixed surface.
1156-1165
Electronic Edition (ACM DL) BibTeX
- Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi:
Additive approximation algorithms for list-coloring minor-closed class of graphs.
1166-1175
Electronic Edition (ACM DL) BibTeX
- Zdenek Dvorak, Ken-ichi Kawarabayashi, Robin Thomas:
Three-coloring triangle-free planar graphs in linear time.
1176-1182
Electronic Edition (ACM DL) BibTeX
- Ken-ichi Kawarabayashi, Bruce A. Reed:
A nearly linear time algorithm for the half integral parity disjoint paths packing problem.
1183-1192
Electronic Edition (ACM DL) BibTeX
- Boaz Barak, Moritz Hardt, Satyen Kale:
The uniform hardcore lemma via approximate Bregman projections.
1193-1200
Electronic Edition (ACM DL) BibTeX
- Anthony Man-Cho So:
Improved approximation bound for quadratic optimization problems with orthogonality constraints.
1201-1209
Electronic Edition (ACM DL) BibTeX
- Khaled M. Elbassioni, Rajiv Raman, Saurabh Ray, René Sitters:
On the approximability of the maximum feasible subsystem problem with 0/1-coefficients.
1210-1219
Electronic Edition (ACM DL) BibTeX
- Amitabh Basu, Pierre Bonami, Gérard Cornuéjols, François Margot:
On the relative strength of split, triangle and quadrilateral cuts.
1220-1229
Electronic Edition (ACM DL) BibTeX
- Satoru Iwata, James B. Orlin:
A simple combinatorial algorithm for submodular function minimization.
1230-1237
Electronic Edition (ACM DL) BibTeX
- Nikhil Bansal, Ho-Leung Chan:
Weighted flow time does not admit O(1)-competitive algorithms.
1238-1244
Electronic Edition (ACM DL) BibTeX
- Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar:
Secretary problems: weights and discounts.
1245-1254
Electronic Edition (ACM DL) BibTeX
- Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup:
Stream sampling for variance-optimal estimation of subset sums.
1255-1264
Electronic Edition (ACM DL) BibTeX
- Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pál:
An online mechanism for ad slot reservations with cancellations.
1265-1274
Electronic Edition (ACM DL) BibTeX
- Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh, Prabhakar Raghavan:
Online story scheduling in web advertising.
1275-1284
Electronic Edition (ACM DL) BibTeX
Copyright © Sat May 16 23:41:54 2009
by Michael Ley (ley@uni-trier.de)
