Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms
Edited by Moses Charikar
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 10), 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 Best
Paper Presentation 4A 4B 4C 5A 5B 5C 6 7A 7B 7C 8A 8B 8C 9A 9B 9C 10 11A 11B 11C 12A 12B 12C
1 On
the Optimality of Spiral Search
Elmar
Langetepe
13 An
Improved Competitive Algorithm for Reordering Buffer Management
Noa
Avigdor-Elgrabli and Yuval Rabani
22 How
to Meet Asynchronously (Almost) Everywhere
Jurek
Czyzowicz, Arnaud Labourel, and Andrzej Pelc
31 A
1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order
Arrival Model
Bahman
Bahmani, Aranyak Mehta, and Rajeev Motwani
40 Towards
the Randomized k-Server Conjecture: A Primal-Dual Approach
Nikhil
Bansal, Niv Buchbinder, and Joseph (Seffi) Naor
56 Testing
Monotone Continuous Distributions on High-dimensional Real Cubes
Michał Adamaszek,
Artur Czumaj, and Christian Sohler
66 Property
Testing and Parameter Testing for Permutations
Carlos
Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, and Rudini Menezes Sampaio
76 Near-Optimal
Sublinear Time Algorithms for Ulam Distance
Alexandr
Andoni and Huy L. Nguyen
87 Lower
Bounds for Testing Triangle-freeness in Boolean Functions
Arnab
Bhattacharyya and Ning Xie
99 Counting
Stars and Other Small Subgraphs in Sublinear Time
Mira
Gonen, Dana Ron, and Yuval Shavitt
117 Cell-Probe
Lower Bounds for Succinct Partial Sums
Mihai
Pătraşcu and Emanuele Viola
123 On
the Cell Probe Complexity of Dynamic Membership
Ke Yi
and Qin Zhang
134 Fully-Functional
Succinct Trees
Kunihiko
Sadakane and Gonzalo Navarro
150 Data
Structures for Range Minimum Queries in Multidimensional Arrays
Hao
Yuan and Mikhail J. Atallah
161 Counting
Inversions, Offline Orthogonal Range Counting, and Related Problems
Timothy
M. Chan and Mihai Pătraşcu
174 Differential
Privacy in New Settings
Cynthia
Dwork
184 Lower
Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities
Alexandr
Andoni, T. S. Jayram, and Mihai Pătraşcu
193 Genus
and the Geometry of the Cut Graph
James
R. Lee and Anastasios Sidiropoulos
202 Testing
Planarity of Partially Embedded Graphs
Patrizio
Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek,
Jan Kratochvíl, Maurizio Patrignani, and
Ignaz Rutter
222 Inapproximability
for Planar Embedding Problems
Jeff
Edmonds, Anastasios Sidiropoulos, and Anastasios Zouzias
236 Towards
a Calculus for Non-Linear Spectral Gaps
Manor
Mendel and Assaf Naor
256 A
QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics
T-H.
Hubert Chan and Khaled Elbassioni
268 PTAS
for Maximum Weight Independent Set Problem with Random Weights in Bounded
Degree Graphs
David
Gamarnik, David Goldberg, and Theophane Weber
279 Belief
Propagation for Min-cost Network Flow: Convergence & Correctness
David
Gamarnik, Devavrat Shah, and Yehua Wei
293 Finding
the Jaccard Median
Flavio
Chierichetti, Ravi Kumar, Sandeep Pandey, and Sergei Vassilvitskii
312 The
Focus of Attention Problem
Dries
Goossens, Sergey Polyakovskiy, Frits C. R. Spieksma, and Gerhard J. Woeginger
318 Recognizing
a Totally Odd K4-subdivision, Parity 2-disjoint Rooted Paths and
a Parity Cycle Through Specified Elements
Ken-ichi
Kawarabayashi, Zhentao Li, and Bruce Reed
329 Decomposition,
Approximation, and Coloring of Odd-Minor-Free Graphs
Erik
D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi
345 The
Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs
Ken-ichi
Kawarabayashi and Yusuke Kobayashi
354 On
Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order
Logic
Stephan
Kreutzer and Siamak Tazari
365 An
(almost) Linear Time Algorithm for Odd Cyles Transversal
Ken-ichi
Kawarabayashi and Bruce Reed
379 An O(log n/
log log n)-approximation Algorithm for the Asymmetric Traveling
Salesman Problem
Arash
Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and
Amin Saberi
390 A
Quasi-polynomial Time Approximation Scheme for Euclidean Capacitated Vehicle
Routing
Aparna
Das and Claire Mathieu
404 Region
Growing for Multi-Route Cuts
Siddharth
Barman and Shuchi Chawla
419 Asymmetric
Traveling Salesman Path and Directed Latency Problems
Zachary
Friggstad, Mohammad R. Salavatipour, and Zoya Svitkina
429 Improved
Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting
Strolls
Aaron
Archer and Anna Blasiak
448 Quantum
Algorithms for Highly Non-Linear Boolean Functions
Martin
Rötteler
458 Compact
Ancestry Labeling Schemes for XML Trees
Pierre
Fraigniaud and Amos Korman
467 Generating
a d-dimensional Linear Subspace Efficiently
Raphael
Yuster
471 Algorithms
for Ray Class Groups and Hilbert Class Fields
Kirsten
Eisenträger and Sean Hallgren
484 A
Space—Time Tradeoff for Permutation Problems
Mikko
Koivisto and Pekka Parviainen
493 Algorithmic
Lower Bounds for Problems Parameterized with Clique-Width
Fedor
V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh
503 Bidimensionality
and Kernels
Fedor
V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos
511 Solving
MAX-r-SAT Above a Tight Lower Bound
Noga
Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, and Anders Yeo
518 Inapproximability
for VCG-Based Combinatorial Auctions
Dave
Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos
Papadimitriou, Michael Schapira, Yaron Singer, and
Chris Umans
537 Price
of Anarchy for Greedy Auctions
B. Lucier
and A. Borodin
554 Incentive
Compatible Budget Elicitation in Multi-unit Auctions
Sayan
Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia
573 Utilitarian
Mechanism Design for Multi-Objective Optimization
Fabrizio
Grandoni, Piotr Krysta, Stefano Leonardi, and Carmine Ventre
585 Pricing
Randomized Allocations
Patrick
Briest, Shuchi Chawla, Robert Kleinberg, and S. Matthew Weinberg
598 Universal ε-approximators
for Integrals
Michael
Langberg and Leonard J. Schulman
608 Optimally
Reconstructing Weighted Graphs Using Queries
Hanna
Mazzawi
616 Online
Learning with Queries
Chao-Kai
Chiang and Chi-Jen Lu
630 Coresets
and Sketches for High Dimensional Subspace Approximation Problems
Dan
Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff
650 Convergence,
Stability, and Discrete Approximation of Laplace Spectra
Tamal
K. Dey, Pawas Ranjan, and Yusu Wang
664 Sharp
Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities
Subhash
Khot and Assaf Naor
684 Fast
SDP Algorithms for Constraint Satisfaction Problems
David
Steurer
698 Probabilistic
Analysis of the Semidefinite Relaxation Detector in Digital Communications
Anthony
Man-Cho So
712 Correlation
Clustering with Noisy Input
Claire
Mathieu and Warren Schudy
729 A
Polynomial Time Approximation Scheme for k-Consensus Clustering
Tom
Coleman and Anthony Wirth
741 Google’s
Auction for TV Ads
Noam
Nisan
742 A
Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest
Simple Paths in General Graphs
Aaron
Bernstein
756 Solving
the Replacement Paths Problem for Planar Directed Graphs in O (n log n)
Time
Christian
Wulff-Nilsen
766 Bounding
Variance and Expectation of Longest Path Lengths in DAGs
Jeff
Edmonds and Supratik Chakraborty
782 Highway
Dimension, Shortest Paths, and Provably Efficient Algorithms
Ittai
Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck
794 Maximum
Flows and Parametric Shortest Paths in Planar Graphs
Jeff
Erickson
805 On
the Equilibria of Alternating Move Games
Aaron
Roth, Maria Florina Balcan, Adam Kalai, and Yishay Mansour
817 Monotonicity
in Bargaining Networks
Yossi
Azar, Nikhil R. Devanur, Kamal Jain, and Yuval Rabani
827 Sharp
Dichotomies for Regret Minimization in Metric Spaces
Robert
Kleinberg and Aleksandrs Slivkins
847 Solving
Simple Stochastic Tail Games
Hugo
Gimbert and Florian Horn
863 One-Counter
Markov Decision Processes
T. Brázdil,
V. Brožek, K. Etessami, A. Kučera, and D. Wojtczak
875 On
Nonlinear Forbidden 0-1 Matrices: A Refutation of a Füredi-Hajnal Conjecture
Seth
Pettie
886 An
Improved Construction of Progression-Free Sets
Michael
Elkin
906 Geometric
Optimization and Sums of Algebraic Functions
Antoine
Vigneron
918 Approximating
the Crossing Number of Graphs Embeddable in Any Orientable Surface
Petr
Hliněný and Markus Chimani
928 How
Far Can You Reach?
Ciprian
Borcea and Ileana Streinu
938 A
Model of Computation for MapReduce
Howard
Karloff, Siddharth Suri, and Sergei Vassilvitskii
949 Synchrony
and Asynchrony in Neural Networks
Fabian
Kuhn, Konstantinos Panagiotou, Joel Spencer, and Angelika Steger
965 Distributed
Agreement with Optimal Communication Complexity
Seth
Gilbert and Dariusz R. Kowalski
978 How
Good is the Chord Algorithm?
Constantinos
Daskalakis, Ilias Diakonikolas, and Mihalis Yannakakis
992 Deterministic
Algorithms for the Lovász Local Lemma
Karthekeyan
Chandrasekaran, Navin Goyal, and Bernhard Haeupler
1005 A
Deterministic Truthful PTAS for Scheduling Related Machines
George
Christodoulou and Annamária Kovács
1017 A
Fourier Space Algorithm for Solving Quadratic Assignment Problems
Risi
Kondor
1029 EDF-schedulability
of Synchronous Periodic Task Systems is coNP-hard
Friedrich
Eisenbrand and Thomas Rothvoβ
1035 Reconstructing
Approximate Phylogenetic Trees from Quartet Samples
Sagi
Snir and Raphael Yuster
1045 Shape
Replication through Self-Assembly and RNase Enzymes
Zachary
Abel, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin
Flatland, Scott D. Kominers, and Robert Schweller
1065 On
the Possibility of Faster SAT Algorithms
Mihai
Pǎtraşcu and Ryan Williams
1076 Paired
Approximation Problems and Incompatible Inapproximabilities
David
Eppstein
1087 Correlation
Robust Stochastic Optimization
Shipra
Agrawal, Yichuan Ding, Amin Saberi, and Yinyu Ye
1097 Approximability
of Robust Network Design
Neil
Olver and F. Bruce Shepherd
1106 Differentially
Private Combinatorial Optimization
Anupam
Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar
1126 Efficiently
Decodable Non-adaptive Group Testing
Piotr
Indyk, Hung Q. Ngo, and Atri Rudra
1143 1-Pass
Relative-Error L>p-Sampling with Applications
Morteza
Monemizadeh and David P. Woodruff
1161 On
the Exact Space Complexity of Sketching and Streaming Small Norms
Daniel
M. Kane, Jelani Nelson, and David P. Woodruff
1179 A
Locality-Sensitive Hash for Real Vectors
Tyler
Neylon
1190 Lower
Bounds for Sparse Recovery
Khanh
Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff
1198 Flow-Cut
Gaps for Integer and Fractional Multiflows
Chandra
Chekuri, F. Bruce Shepherd, and Christophe Weibel
1209 A
Max-Flow/Min-Cut Algorithm for a Class of Wireless Networks
S. M.
Sadegh Tabatabaei Yazdi and Serap A. Savari
1227 Testing
Additive Integrality Gaps
Friedrich
Eisenbrand, Nicolai Hähnle, Dömötör Pálvölgyi,
and Gennady Shmonin
1235 Classified
Stable Matching
Chien-Chung
Huang
1254 Basis
Reduction and the Complexity of Brand-and-Bound
Gábor
Pataki, Mustafa Tural, and Erick B. Wong
1262 Randomized
Shellsort: A Simple Oblivious Sorting Algorithm
Michael
T. Goodrich
1278 Data-Specific
Analysis of String Sorting
Raimund
Seidel
1287 Fast
Distance Multiplication of Unit-Monge Matrices
Alexander
Tiskin
1297 Regular
Expression Matching with Multi-Strings and Intervals
Philip
Bille and Mikkel Thorup
1309 Road
Network Reconstruction for Organizing Paths
Daniel
Chen, Leonidas J. Guibas, John Hershberger, and Jian Sun
1321 The
Power of Convex Relaxation: The Surprising Stories of Matrix Completion and
Compressed Sensing
Emmanuel
J. Candes
1322 An
Online Scalable Algorithm for Average Flow Time in Broadcast Scheduling
Sungjin
Im and Benjamin Moseley
1334 Resource
Minimization for Fire Containment
Parinya
Chalermsook and Julia Chuzhoy
1350 Algorithms
and Complexity for Periodic Real-Time Scheduling
Vincenzo
Bonifaci, Ho-Leung Chan, Alberto Marchetti-Spaccamela, and Nicole Megow
1360 Energy
Efficient Scheduling via Partial Shutdown
Samir
Khuller, Jian Li, and Barna Saha
1373 SRPT
is 1.86-Competitive for Completion Time Scheduling
Christine
Chung, Tim Nonner, and Alexander Souza
1389 The
Rank of Diluted Random Graphs
Charles
Bordenave and Marc Lelarge
1403 The
Scaling Window for a Random Graph with a Given Degree Sequence
Hamed
Hatami and Michael Molloy
1412 Efficient
Broadcast on Random Geometric Graphs
Milan
Bradonjić, Robert Elsässer, Tobias Friedrich, Thomas Sauerwald, and
Alexandre Stauffer
1422 Speeding
Up Random Walks with Neighborhood Exploration
Petra Berenbrink,
Colin Cooper, Robert Elsässer, Tomasz Radzik, and Thomas Sauerwald
1436 Vertices
of Degree k in Random Maps
Daniel
Johannsen and Konstantinos Panagiotou
1448 Cache-Oblivious
Dynamic Dictionaries with Update/Query Tradeoffs
Gerth
Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono,
Stefan Langerman, and J. Ian Munro
1457 Applications
of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures
Seth
Pettie
1468 Faster
Exponential Time Algorithms for the Shortest Vector Problem
Daniele
Micciancio and Panagiotis Voulgaris
1481 Streaming
Algorithms for Extent Problems in High Dimensions
Pankaj
K. Agarwal and R. Sharathkumar
1490 Deletion
Without Rebalancing in Balanced Binary Trees
Siddhartha
Sen and Robert E. Tarjan
1500 On
Linear and Semidefinite Programming Relaxations for Hypergraph Matching
Yuk
Hei Chan and Lap Chi Lau
1512 Partition
Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph
Attila
Bernáth, Roland Grappe, and Zoltán Szigeti
1521 Tree
Embeddings for Two-Edge-Connected Network Design
Anupam
Gupta, Ravishankar Krishnaswamy, and R. Ravi
1539 A
Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
Nikhil
Bansal, Anupam Gupta, and Ravishankar Krishnaswamy
1546 Self-improving
Algorithms for Convex Hulls
Kenneth
L. Clarkson, Wolfgang Mulzer, and C. Seshadhri
1566 The
Forest Hiding Problem
Adrian
Dumitrescu and Minghui Jiang
1580 Terrain
Guarding is NP-Hard
James
King and Erik Krohn
1594 Hardness
Results for Homology Localization
Chao
Chen and Daniel Freedman
1605 Orthogonal
Ham-Sandwich Theorem in R3
Sergey
Bereg
1613 The
(1 + β)-Choice Process and Weighted Balls-into-Bins
Yuval
Peres, Kunal Talwar, and Udi Wieder
1620 Quasirandom
Load Balancing
Tobias
Friedrich, Martin Gairing, and Thomas Sauerwald
1630 Thin
Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped
Bodies
Karthekeyan
Chandrasekaran, Daniel Dadush, and Santosh Vempala
1646 Phase
Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular
Trees
Prasad
Tetali, Juan C. Vera, Eric Vigoda, and Linji Yang
1657 Rumour
Spreading and Graph Conductance
Flavio
Chierichetti, Silvio Lattanzi, and Alessandro Panconesi
