Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms
Edited by Claire Mathieu
Each link below is to a PDF of the paper as it was submitted. Papers are listed in program order. PDF file names represent the Proceedings (SODA and year 09), followed by order in printed version (e.g. 001) and first author's last name and first initial.
Table of Contents
Sessions:
1A 1B 1C 2 3A 3B 3C 4A 4B 4C 5A 5B 5C 6 7A 7B 7C 8A 8B 8C 9A 9B 9C 10 11A 11B 11C 12A 12B 12C
1 Improved
Bounds and New Techniques for Daveport–Schinzel Sequences and Their
Generalizations
Gabriel Nivasch
11 Perfect
Matchings via Uniform Sampling in Regular Bipartite Graphs
Ashish
Goel, Michael Kapralov, and Sanjeev Khanna
18 The
Ratio Index for Budgeted Learning, with Applications
Ashish Goel,
Sanjeev Khanna, and Brad Null
28 Approximation
Algorithms for Restless Bandit Problems
Sudipto
Guha, Kamesh Munagala, and Peng Shi
38 Better
Algorithms for Benign Bandits
Elad Hazan
and Satyen Kale
48 The
Cover Time of Random Geometric Graphs
Colin
Cooper and Alan Frieze
58 The
Complexity of Simulating Brownian Motion
Ilia
Binder and Mark Braverman
68 Sorting
by Placement and Shift
Sergi
Elizalde and Peter Winkler
76 Sampling
Biased Lattice Configurations Using Exponential Metrics
Sam
Greenberg, Amanda Pascoe, and Dana Randall
86 On
the Hitting Times of Quantum Versus Random Walks
Frédéric
Magniez, Ashwin Nayak, Peter C. Richter, and Miklos Santha
96 Efficient
Algorithms for the 2-Gathering Problem
Alon
Shalita and Uri Zwick
106 Asymptotically
Optimal Frugal Colouring
Michael
Molloy and Bruce Reed
115 A
Quadratic Kernel for Feedback Vertex Set
Stéphan
Thomassé
120 Coloring
Triangle-Free Graphs on Surfaces
Zdeněk
Dvořák, Daniel Král, and Robin Thomas
130 (Un)Expected
Behavior of Digital Search Tree Profile
Michael
Drmota and Wojciech Szpankowski
139 Combinatorial
Stochastic Processes and Nonparametric Bayesian Modeling
Michael
I. Jordan
140 Comparison-Based
Time–Space Lower Bounds for Selection
Timothy
M. Chan
150 Linear-Time
Algorithms for Geometric Graphs with Sublinearly Many Crossings
David
Eppstein, Michael T. Goodrich, and Darren Strash
160 Self-Overlapping
Curves Revisited
David
Eppstein and Elena Mumford
170 Line
Transversals of Convex Polyhedra in R3
Haim
Kaplan, Natan Rubin, and Micha Sharir
180 Optimal
Halfspace Range Reporting in Three Dimensions
Peyman
Afshani and Timothy M. Chan
187 Optimality
of Belief Propagation for Random Assignment Problem
J. Salez
and D. Shah
197 Termination
Criteria for Solving Concurrent Safety and Reachability Games
Krishnendu
Chatterjee, Luca de Alfaro, and Thomas A. Henzinger
207 An
Efficient Sparse Regularity Concept
Amin
Coja-Oghlan, Colin Cooper, and Alan Frieze
217 Almost
All Hypergraphs without Fano Planes Are Bipartite
Yury
Person and Mathias Schacht
227 Hypergraph
Regularity and Quasi-Randomness
Brendan
Nagle, Annika Poerschke, Vojtěch Rödl, and Mathias Schacht
236 Shortest
Paths in Directed Planar Graphs with Negative Lengths: A Linear-Space O(n log2 n)- Time
Algorithm
Philip
Klein, Shay Mozes, and Oren Weimann
246 A
Near-Linear Time Algorithm for Constructing a Cactus Representation of Minimum
Cuts
David
R. Karger and Debmalya Panigrahi
256 Testing
Halfspaces
Kevin
Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A. Servedio
265 Fast
Edge Orientation for Unweighted Graphs
Anand
Bhalgat and Ramesh Hariharan
273 A
Unified Approach to Distance-Two Colouring of Planar Graphs
Omid
Amini, Louis Esperet, and Jan van den Heuvel
283 Approximate
Euclidean Shortest Paths amid Convex Obstacles
Pankaj
K. Agarwal, R. Sharathkumar, and Hai Yu
293 Approximate
Line Nearest Neighbor in High Dimensions
Alexandr
Andoni, Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen
302 Decomposition
of Multiple Coverings into More Parts
Greg
Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David
Orden, and Pedro Ramos
311 On
Stars and Steiner Stars. II
Adrian
Dumitrescu, Csaba D. Tóth, and Guangwu Xu
318 Combinatorial
Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design
Yury
Lifshits and Shengyu Zhang
327 Computing
the Nucleolus of Weighted Voting Games
Edith
Elkind and Dmitrii Pasechnik
336 High
Rate Fingerprinting Codes and the Fingerprinting Capacity
Ehsan
Amiri and Gábor Tardos
346 On
the Power of Two, Three and Four Probes
Noga
Alon and Uriel Feige
355 Exponential
Lower Bounds and Integrality Gaps for Tree-Like Lovász–Schrijver
Procedures
Toniann
Pitassi and Nathan Segerlind
365 3-Bit
Dictator Testing: 1 vs. 5/8
Ryan
O’Donnell and Yi Wu
375 Inserting
a Vertex into a Planar Graph
Markus
Chimani, Carsten Gutwenger, Petra Mutzel, and Christian Wolf
384 Fast
Algorithms for (max, min)-Matrix Multiplication and Bottleneck Shortest Paths
Ran
Duan and Seth Pettie
392 Sorting
and Selection in Posets
Constantinos
Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, and Elad
Verbin
402 Finding
Duplicates in a Data Stream
Parikshit
Gopalan and Jaikumar Radhakrishnan
412 Compressed
Counting
Ping
Li
422 Natural
Algorithms
Bernard
Chazelle
432 Maximal
Biconnected Subgraphs of Random Planar Graphs
Konstantinos
Panagiotou and Angelika Steger
441 Approximate
Shared-Memory Counting Despite a Strong Adversary
James
Aspnes and Keren Censor
451 On
Smoothes k-CNF Formulas and the Walksat Algorithm
Amin
Coja-Oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich, and Dan Vilenchik
461 Improved
Smoothed Analysis of the k-Means Method
Bodo
Manthey and Heiko Röglin
471 Pairing
Heaps with O(log log n) Decrease Cost
Amr
Elmasry
477 A
Simpler Implementation and Analysis of Chazelle’s Soft Heaps
Haim
Kaplan and Uri Zwick
486 Biased
Range Trees
Vida
Dujmović, John Howat, and Pat Morin
496 The
Geometry of Binary Search Trees
Erik
D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pǎtraşcu
506 Dual-Failure
Distance and Connectivity Oracles
Ran
Duan and Seth Pettie
516 On
the Maximum Quadratic Assignment Problem
Viswanath
Nagarajan and Maxim Sviridenko
525 Towards
Computing the Grothendieck Constant
Prasad
Raghavendra and David Steurer
535 Approximating
Submodular Functions Everywhere
Michel
X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, and Vahab Mirrokni
545 Maximizing
Submodular Set Functions Subject to Multiple Linear Constraints
Ariel
Kulik, Hadas Shachnai, and Tami Tamir
555 Combinatorial
Algorithms for Wireless Information Flow
Aurore
Amaudruz and Christina Fragouli
565 Probability,
Algorithms and Complexity
Volker
Strassen
566 Generating
Random Graphs with Large Girth
Mohsen
Bayati, Andrea Montanari, and Amin Saberi
576 Expanders
via Random Spanning Trees
Navin
Goyal, Luis Rademacher, and Santosh Vempala
586 The
Extended k-Tree Algorithm
Lorenz
Minder and Alistair Sinclair
596 Sequential
Cavity Method for Computing Limits of the Log-Partition Function for Lattice
Models
David
Gamarnik and Dmitriy Katz
606 A
Universally Fastest Algorithms for Max 2-Sat, Max 2-CSP, and Everything in
Between
Serge
Gaspers and Gregory B. Sorkin
616 Finding
Shortest Contractible and Shortest Separating Cycles in Embedded Graphs
Sergio
Cabello
625 Cell
Probe Lower Bounds for Succinct Data Structures
Alexander
Golynski
635 Succinct
Geometric Indexes Supporting Point Location Queries
Prosenjit
Bose, Eric Y. Chen, Meng He, Anil Maheshwari, and Pat Morin
645 Exact
Algorithms for Partial Curve Matching via the Fréchet Distance
Kevin
Buchin, Maike Buchin, and Yusu Wang
655 String
Hashing for Linear Probing
Mikkel
Thorup
665 Parameterized
Approximation Scheme for the Multiple Knapsack Problem
Klaus
Jansen
675 Improved
Approximation Algorithms for Scheduling with Fixed Jobs
Florian
Diedrich and Klaus Jansen
685 Scalably
Scheduling Processes with Arbitrary Speedup Curves
Jeff
Edmonds and Kirk Pruhs
693 Speed
Scaling with an Arbitrary Power Function
Nikhil
Bansal, Ho-Leung Chan, and Kirk Pruhs
702 A
Logarithmic Approximation for Unsplittable Flow on Line Graphs
Nikhil
Bansal, Zachary Friggstad, Rohit Khandekar, and Mohammad R. Salavatipour
710 On
the Complexity of Nash Equilibria of Action-Graph Games
Constantinos
Daskalakis, Grant Schoenebeck, Gregory Valiant, and Paul Valiant
720 How
Hard Is It to Approximate the Best Nash Equilibrium?
Elad
Hazan and Robert Krauthgamer
728 Improved
Equilibria via Public Service Advertising
Maria-Florina
Balcan, Avrim Blum, and Yishay Mansour
738 Stepwise
Randomized Combinatorial Auctions Achieve Revenue Monotonicity
Baharak
Rastegari, Anne Condon, and Kevin Leyton-Brown
748 Equilibria
of Atomic Flow Games Are not Unique
Umang
Bhaskar, Lisa Fleischer, Darrell Hoy, and Chien-Chung Huang
758 A
Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding
Mordecai
Golin, Xiaoming Xu, and Jiajin Yu
768 On
the Bit-Complexity of Lempel–Ziv Compression
Paolo
Ferragina, Igor Nitto, and Rossano Venturini
778 From
Coding Theory to Efficient Pattern Matching
Raphaël
Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild
785 Monotone
Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses
Djamal
Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna
795 On
Risks of Using Cuckoo Hashing with Simple Universal Hash Classes
Martin
Dietzfelbinger and Ulf Schellbach
805 Assignment
Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility
Location
Mohammad
Hossein Bateni and MohammadTaghi Hajiaghayi
815 Efficient
Coordination Mechanisms for Unrelated Machine Scheduling
Ioannis
Caragiannis
825 Clique-Width:
On the Price of Generality
Fedor
V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh
835 Reasoning
about Online Algorithms with Weighted Automata
Benjamin
Aminof, Orna Kupferman, and Robby Lampert
845 Appointment
Scheduling with Discrete Random Durations
Mehmet
A. Begen and Maurice Queyranne
855 Hardness
of Embedding Simplicial Complexes in Rd
Jiří Matoušek,
Martin Tancer, and Uli Wagner
865 Overcoming
the ℓ1 Non-Embeddability Barrier: Algorithms for Product Metrics
Alexandr
Andoni, Piotr Indyk, and Robert Krauthgamer
875 On
Low Dimensional Local Embeddings
Ittai
Abraham, Yair Bartal, and Ofer Neiman
885 The
Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, but Not
Quite
William
B. Johnson and Assaf Naor
892 Maximum
Independent Set of Rectangles
Parinya
Chalermsook and Julia Chuzhoy
902 Approximating
Fractional Hypertree Width
Dániel
Marx
912 An
Almost O(log k)-Approximation for k-Connected Subgraphs
Zeev
Nutov
922 Improved
Approximating Algorithms for Directed Steiner Forest
Moran
Feldman, Guy Kortsarz, and Zeev Nutov
932 Transitive-Closure
Spanners
Arnab
Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, and David
P. Woodruff
942 Partitioning
Graphs into Balanced Components
Robert
Krauthgamer, Joseph (Seffi) Naor, and Roy Schwartz
950 Efficient
Algorithms on Sets of Permutations, Dominance, and Real-Weighted APSP
Raphael
Yuster
958 Discounted
Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths
Omid
Madani, Mikkel Thorup, and Uri Zwick
968 An
Improved Approximation Algorithm for the Column Subset Selection Problem
Christos
Boutsidis, Michael W. Mahoney, and Petrol Drineas
978 Column
Subset Selection, Matrix Factorization, and Eigenvalue Optimization
Joel
A. Tropp
987 Loopless
Generation of Multiset Permutations Using a Constant Number of Variables by
Prefix Shifts
Aaron
Williams
997 The
Unreasonable Effectiveness of Martingales
Yuval
Peres
1001 Dimension
Detection via Slivers
Siu-Wing
Cheng and Man-Kwun Chiu
1011 Persistent
Homology for Kernels, Images, and Cokernels
David
Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov
1021 Analysis
of Scalar Fields over Point Cloud Data
Frédéric
Chazal, Leonidas J. Guibas, Steve Y. Oudot, and Primoz Skraba
1031 Constructing
Laplace Operator from Point Clouds in Rd
Mikhail
Belkin, Jian Sun, and Yusu Wang
1041 Size Complexity
of Volume Meshes vs. Surface Meshes
Benoît
Hudson, Gary L. Miller, Todd Phillips, and Don Sheehy
1048 Packing
Mulitway Cuts in Capacitated Graphs
Siddharth
Barman and Shuchi Chawla
1058 On
the Approximability of Dodgson and Young Elections
Ioannis
Caragiannis, Jason A. Covey, Michal Feldman, Christopher M. Homan, Christos Kaklamanis,
Nikos Karanikolas, Ariel D. Procaccia, and Jeffrey S. Rosenschein
1068 Approximate
Clustering without the Approximation
Maria-Florina
Balcan, Avrim Blum, and Anupam Gupta
1078 Robust
PCA and Clustering in Noisy Mixtures
S. Charles
Brubaker
1088 Coresets
and Approximate Clustering for Bregman Divergences
Marcel
R. Ackermann and Johannes Blömer
1098 Multi-Dimensional
Online Tracking
Ke Yi
and Qin Zhang
1108 A New Approach
to Incremental Topological Ordering
Michael
A. Bender, Jeremy T. Fineman, and Seth Gilbert
1116 Online
Scheduling to Minimize the Maximum Delay Factor
Chandra
Chekuri and Benjamin Moseley
1126 Collecting
Weighted Items from a Dynamic Queue
Marcin
Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Łukasz Jeż,
and Grzegorz Stachowiak
1136 Paging
and List Update under Bijective Analysis
Spyros
Angelopoulos and Pascal Schweitzer
1146 Algorithms
for Finding an Induced Cycle in Planar Graphs and Bounded Genus Graphs
Yusuke
Kobayashi and Ken-ichi Kawarabayashi
1156 List-Color-Critical
Graphs on a Fixed Surface
Ken-ichi
Kawarabayashi and Bojan Mohar
1166 Additive
Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs
Ken-ichi
Kawarabayashi, Erik D. Demaine, and MohammadTaghi Hajiaghayi
1176 Three-Coloring
Triangle-Free Planar Graphs in Linear Time
Zdeněk
Dvořák, Ken-ichi Kawarabayashi, and Robin Thomas
1183 A
Nearly Linear Time Algorithms for the Half Integral Parity Disjoint Paths Packing
Problem
Ken-ichi
Kawarabayashi and Bruce Reed
1193 The Uniform
Hardcore Lemma via Approximate Bregman Projections
Boaz
Barak, Moritz Hardt, and Satyen Kale
1201 Improved Approximation
Bound for Quadratic Optimization Problems with Orthogonality Constraints
Anthony
Man-Cho So
1210 On
the Approximability of the Maximum Feasible Subsystem Problem with 0/1-Coefficients
Khaled
Elbassioni, Rajiv Raman, Saurabh Ray, and René Sitters
1220 On the Relative
Strength of Split, Triangle and Quadrilateral Cuts
Amitabh
Basu, Pierre Bonami, Gérard Cornuéjols, and François Margot
1230 A Simple
Combinatorial Algorithm for Submodular Function Minimization
Satoru
Iwata and James B. Orlin
1238 Weighted
Flow Time Does not Admit O(1)-Competitive Algorithms
Nikhil
Bansal and Ho-Leung Chan
1245 Secretary
Problems: Weights and Discounts
Moshe
Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, and Kunal Talwar
1255 Stream Sampling
for Variance-Optimal Estimation of Subset Sums
Edith
Cohen, Nick Duffield, Haim Kaplan, Carsten Lund, and Mikkel Thorup
1265 An
Online Mechanism for Ad Slot Reservations with Cancellations
Florin Constantin,
Jon Feldman, S. Muthukrishnan, and Martin Pál
1275 Online
Story Scheduling in Web Advertising
Anirban
Dasgupta, Arpita Ghosh, Hamid Nazerzadeh, and Prabhakar Raghavan
