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
- Gabriel Nivasch:
Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations.
1-10

- Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect matchings via uniform sampling in regular bipartite graphs.
11-17

- Ashish Goel, Sanjeev Khanna, Brad Null:
The ratio index for budgeted learning, with applications.
18-27

- Sudipto Guha, Kamesh Munagala, Peng Shi:
Approximation algorithms for restless bandit problems.
28-37

- Elad Hazan, Satyen Kale:
Better algorithms for benign bandits.
38-47

- Colin Cooper, Alan M. Frieze:
The cover time of random geometric graphs.
48-57

- Ilia Binder, Mark Braverman:
The complexity of simulating Brownian Motion.
58-67

- Sergi Elizalde, Peter Winkler:
Sorting by placement and shift.
68-75

- Sam Greenberg, Amanda Pascoe, Dana Randall:
Sampling biased lattice configurations using exponential metrics.
76-85

- Frédéric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha:
On the hitting times of quantum versus random walks.
86-95

- Alon Shalita, Uri Zwick:
Efficient algorithms for the 2-gathering problem.
96-105

- Michael Molloy, Bruce A. Reed:
Asymptotically optimal frugal colouring.
106-114

- Stéphan Thomassé:
A quadratic kernel for feedback vertex set.
115-119

- Zdenek Dvorak, Daniel Král, Robin Thomas:
Coloring triangle-free graphs on surfaces.
120-129

- Michael Drmota, Wojciech Szpankowski:
(Un)expected behavior of digital search tree profile.
130-138

- Michael I. Jordan:
Combinatorial stochastic processes and nonparametric Bayesian modeling.
139

- Timothy M. Chan:
Comparison-based time-space lower bounds for selection.
140-149

- David Eppstein, Michael T. Goodrich, Darren Strash:
Linear-time algorithms for geometric graphs with sublinearly many crossings.
150-159

- David Eppstein, Elena Mumford:
Self-overlapping curves revisited.
160-169

- Haim Kaplan, Natan Rubin, Micha Sharir:
Line transversals of convex polyhedra in R3.
170-179

- Peyman Afshani, Timothy M. Chan:
Optimal halfspace range reporting in three dimensions.
180-186

- J. Salez, D. Shah:
Optimality of belief propagation for random assignment problem.
187-196

- Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger:
Termination criteria for solving concurrent safety and reachability games.
197-206

- Amin Coja-Oghlan, Colin Cooper, Alan M. Frieze:
An efficient sparse regularity concept.
207-216

- Yury Person, Mathias Schacht:
Almost all hypergraphs without Fano planes are bipartite.
217-226

- Brendan Nagle, Annika Poerschke, Vojtech Rödl, Mathias Schacht:
Hypergraph regularity and quasi-randomness.
227-235

- Philip N. 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

- David R. Karger, Debmalya Panigrahi:
A near-linear time algorithm for constructing a cactus representation of minimum cuts.
246-255

- Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing halfspaces.
256-264

- Anand Bhalgat, Ramesh Hariharan:
Fast edge orientation for unweighted graphs.
265-272

- Omid Amini, Louis Esperet, Jan van den Heuvel:
A unified approach to distance-two colouring of planar graphs.
273-282

- Pankaj K. Agarwal, R. Sharathkumar, Hai Yu:
Approximate Euclidean shortest paths amid convex obstacles.
283-292

- Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen:
Approximate line nearest neighbor in high dimensions.
293-301

- Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David Orden, Pedro Ramos:
Decomposition of multiple coverings into more parts.
302-310

- Adrian Dumitrescu, Csaba D. Tóth, Guangwu Xu:
On stars and Steiner stars: II.
311-317

- Yury Lifshits, Shengyu Zhang:
Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design.
318-326

- Edith Elkind, Dmitrii V. Pasechnik:
Computing the nucleolus of weighted voting games.
327-335

- Ehsan Amiri, Gábor Tardos:
High rate fingerprinting codes and the fingerprinting capacity.
336-345

- Noga Alon, Uriel Feige:
On the power of two, three and four probes.
346-354

- Toniann Pitassi, Nathan Segerlind:
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.
355-364

- Ryan O'Donnell, Yi Wu:
3-bit dictator testing: 1 vs. 5/8.
365-373

- Markus Chimani, Carsten Gutwenger, Petra Mutzel, Christian Wolf:
Inserting a vertex into a planar graph.
375-383

- Ran Duan, Seth Pettie:
Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths.
384-391

- Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin:
Sorting and selection in posets.
392-401

- Parikshit Gopalan, Jaikumar Radhakrishnan:
Finding duplicates in a data stream.
402-411

- Ping Li:
Compressed counting.
412-421

- Bernard Chazelle:
Natural algorithms.
422-431

- Konstantinos Panagiotou, Angelika Steger:
Maximal biconnected subgraphs of random planar graphs.
432-440

- James Aspnes, Keren Censor:
Approximate shared-memory counting despite a strong adversary.
441-450

- Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik:
On smoothed k-CNF formulas and the Walksat algorithm.
451-460

- Bodo Manthey, Heiko Röglin:
Improved smoothed analysis of the k-means method.
461-470

- Amr Elmasry:
Pairing heaps with O(log log n) decrease cost.
471-476

- Haim Kaplan, Uri Zwick:
A simpler implementation and analysis of Chazelle's soft heaps.
477-485

- Vida Dujmovic, John Howat, Pat Morin:
Biased range trees.
486-495

- Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, Mihai Patrascu:
The geometry of binary search trees.
496-505

- Ran Duan, Seth Pettie:
Dual-failure distance and connectivity oracles.
506-515

- Viswanath Nagarajan, Maxim Sviridenko:
On the maximum quadratic assignment problem.
516-524

- Prasad Raghavendra, David Steurer:
Towards computing the Grothendieck constant.
525-534

- Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni:
Approximating submodular functions everywhere.
535-544

- Ariel Kulik, Hadas Shachnai, Tami Tamir:
Maximizing submodular set functions subject to multiple linear constraints.
545-554

- Aurore Amaudruz, Christina Fragouli:
Combinatorial algorithms for wireless information flow.
555-564

- Volker Strassen:
Probability, algorithms and complexity.
565

- Mohsen Bayati, Andrea Montanari, Amin Saberi:
Generating random graphs with large girth.
566-575

- Navin Goyal, Luis Rademacher, Santosh Vempala:
Expanders via random spanning trees.
576-585

- Lorenz Minder, Alistair Sinclair:
The extended k-tree algorithm.
586-595

- David Gamarnik, Dmitriy Katz:
Sequential cavity method for computing limits of the log-partition function for lattice models.
596-605

- Serge Gaspers, Gregory B. Sorkin:
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.
606-615

- Sergio Cabello:
Finding shortest contractible and shortest separating cycles in embedded graphs.
616-624

- Alexander Golynski:
Cell probe lower bounds for succinct data structures.
625-634

- Prosenjit Bose, Eric Y. Chen, Meng He, Anil Maheshwari, Pat Morin:
Succinct geometric indexes supporting point location queries.
635-644

- Kevin Buchin, Maike Buchin, Yusu Wang:
Exact algorithms for partial curve matching via the Fréchet distance.
645-654

- Mikkel Thorup:
String hashing for linear probing.
655-664

- Klaus Jansen:
Parameterized approximation scheme for the multiple knapsack problem.
665-674

- Florian Diedrich, Klaus Jansen:
Improved approximation algorithms for scheduling with fixed jobs.
675-684

- Jeff Edmonds, Kirk Pruhs:
Scalably scheduling processes with arbitrary speedup curves.
685-692

- Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs:
Speed scaling with an arbitrary power function.
693-701

- Nikhil Bansal, Zachary Friggstad, Rohit Khandekar, Mohammad R. Salavatipour:
A logarithmic approximation for unsplittable flow on line graphs.
702-709

- Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant:
On the complexity of Nash equilibria of action-graph games.
710-719

- Elad Hazan, Robert Krauthgamer:
How hard is it to approximate the best Nash equilibrium?
720-727

- Maria-Florina Balcan, Avrim Blum, Yishay Mansour:
Improved equilibria via public service advertising.
728-737

- Baharak Rastegari, Anne Condon, Kevin Leyton-Brown:
Stepwise randomized combinatorial auctions achieve revenue monotonicity.
738-747

- Umang Bhaskar, Lisa Fleischer, Darrell Hoy, Chien-Chung Huang:
Equilibria of atomic flow games are not unique.
748-757

- Mordecai J. Golin, Xiaoming Xu, Jiajin Yu:
A generic top-down dynamic-programming approach to prefix-free coding.
758-767

- Paolo Ferragina, Igor Nitto, Rossano Venturini:
On the bit-complexity of Lempel-Ziv compression.
768-777

- Raphaël Clifford, Klim Efremenko, Ely Porat, Amir Rothschild:
From coding theory to efficient pattern matching.
778-784

- Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna:
Monotone minimal perfect hashing: searching a sorted table with O(1) accesses.
785-794

- Martin Dietzfelbinger, Ulf Schellbach:
On risks of using cuckoo hashing with simple universal hash classes.
795-804

- MohammadHossein Bateni, MohammadTaghi Hajiaghayi:
Assignment problem in content distribution networks: unsplittable hard-capacitated facility location.
805-814

- Ioannis Caragiannis:
Efficient coordination mechanisms for unrelated machine scheduling.
815-824

- Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
Clique-width: on the price of generality.
825-834

- Benjamin Aminof, Orna Kupferman, Robby Lampert:
Reasoning about online algorithms with weighted automata.
835-844

- Mehmet A. Begen, Maurice Queyranne:
Appointment scheduling with discrete random durations.
845-854

- Jirí Matousek, Martin Tancer, Uli Wagner:
Hardness of embedding simplicial complexes in Rd.
855-864

- Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Overcoming the l1 non-embeddability barrier: algorithms for product metrics.
865-874

- Ittai Abraham, Yair Bartal, Ofer Neiman:
On low dimensional local embeddings.
875-884

- William B. Johnson, Assaf Naor:
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite.
885-891

- Parinya Chalermsook, Julia Chuzhoy:
Maximum independent set of rectangles.
892-901

- Dániel Marx:
Approximating fractional hypertree width.
902-911

- Zeev Nutov:
An almost O(log k)-approximation for k-connected subgraphs.
912-921

- Moran Feldman, Guy Kortsarz, Zeev Nutov:
Improved approximating algorithms for Directed Steiner Forest.
922-931

- Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-closure spanners.
932-941

- Robert Krauthgamer, Joseph Naor, Roy Schwartz:
Partitioning graphs into balanced components.
942-949

- Raphael Yuster:
Efficient algorithms on sets of permutations, dominance, and real-weighted APSP.
950-957

- Omid Madani, Mikkel Thorup, Uri Zwick:
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths.
958-967

- Christos Boutsidis, Michael W. Mahoney, Petros Drineas:
An improved approximation algorithm for the column subset selection problem.
968-977

- Joel A. Tropp:
Column subset selection, matrix factorization, and eigenvalue optimization.
978-986

- Aaron Williams:
Loopless generation of multiset permutations using a constant number of variables by prefix shifts.
987-996

- Yuval Peres:
The unreasonable effectiveness of martingales.
997-1000

- Siu-Wing Cheng, Man-Kwun Chiu:
Dimension detection via slivers.
1001-1010

- David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov:
Persistent homology for kernels, images, and cokernels.
1011-1020

- Frédéric Chazal, Leonidas J. Guibas, Steve Oudot, Primoz Skraba:
Analysis of scalar fields over point cloud data.
1021-1030

- Mikhail Belkin, Jian Sun, Yusu Wang:
Constructing Laplace operator from point clouds in Rd.
1031-1040

- Benoît Hudson, Gary L. Miller, Todd Phillips, Don Sheehy:
Size complexity of volume meshes vs. surface meshes.
1041-1047

- Siddharth Barman, Shuchi Chawla:
Packing multiway cuts in capacitated graphs.
1048-1057

- 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

- Maria-Florina Balcan, Avrim Blum, Anupam Gupta:
Approximate clustering without the approximation.
1068-1077

- S. Charles Brubaker:
Robust PCA and clustering in noisy mixtures.
1078-1087

- Marcel R. Ackermann, Johannes Blömer:
Coresets and approximate clustering for Bregman divergences.
1088-1097

- Ke Yi, Qin Zhang:
Multi-dimensional online tracking.
1098-1107

- Michael A. Bender, Jeremy T. Fineman, Seth Gilbert:
A new approach to incremental topological ordering.
1108-1115

- Chandra Chekuri, Benjamin Moseley:
Online scheduling to minimize the maximum delay factor.
1116-1125

- Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak:
Collecting weighted items from a dynamic queue.
1126-1135

- Spyros Angelopoulos, Pascal Schweitzer:
Paging and list update under bijective analysis.
1136-1145

- Yusuke Kobayashi, Ken-ichi Kawarabayashi:
Algorithms for finding an induced cycle in planar graphs and bounded genus graphs.
1146-1155

- Ken-ichi Kawarabayashi, Bojan Mohar:
List-color-critical graphs on a fixed surface.
1156-1165

- Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi:
Additive approximation algorithms for list-coloring minor-closed class of graphs.
1166-1175

- Zdenek Dvorak, Ken-ichi Kawarabayashi, Robin Thomas:
Three-coloring triangle-free planar graphs in linear time.
1176-1182

- Ken-ichi Kawarabayashi, Bruce A. Reed:
A nearly linear time algorithm for the half integral parity disjoint paths packing problem.
1183-1192

- Boaz Barak, Moritz Hardt, Satyen Kale:
The uniform hardcore lemma via approximate Bregman projections.
1193-1200

- Anthony Man-Cho So:
Improved approximation bound for quadratic optimization problems with orthogonality constraints.
1201-1209

- Khaled M. Elbassioni, Rajiv Raman, Saurabh Ray, René Sitters:
On the approximability of the maximum feasible subsystem problem with 0/1-coefficients.
1210-1219

- Amitabh Basu, Pierre Bonami, Gérard Cornuéjols, François Margot:
On the relative strength of split, triangle and quadrilateral cuts.
1220-1229

- Satoru Iwata, James B. Orlin:
A simple combinatorial algorithm for submodular function minimization.
1230-1237

- Nikhil Bansal, Ho-Leung Chan:
Weighted flow time does not admit O(1)-competitive algorithms.
1238-1244

- Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar:
Secretary problems: weights and discounts.
1245-1254

- Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup:
Stream sampling for variance-optimal estimation of subset sums.
1255-1264

- Florin Constantin, Jon Feldman, S. Muthukrishnan, Martin Pál:
An online mechanism for ad slot reservations with cancellations.
1265-1274

- Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh, Prabhakar Raghavan:
Online story scheduling in web advertising.
1275-1284

Last update Tue May 21 18:04:44 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page