Last update:
Sat Oct 12 12:08:34 MDT 2024
Harold N. Gabow Editor's foreword . . . . . . . . . . . 1--1
Raphael Yuster and
Uri Zwick Fast sparse matrix multiplication . . . 2--13
Jeff Edmonds and
Kirk Pruhs A maiden analysis of longest wait first 14--32
Erik D. Demaine and
Fedor V. Fomin and
Mohammadtaghi Hajiaghayi and
Dimitrios M. Thilikos Fixed-parameter algorithms for $ (k,
r)$-center in planar graphs and map
graphs . . . . . . . . . . . . . . . . . 33--47
Micah Adler and
Dan Rubenstein Pricing multicasting in more flexible
network models . . . . . . . . . . . . . 48--73
Guy Even and
Guy Kortsarz and
Wolfgang Slany On network design problems: fixed cost
flows and the covering Steiner problem 74--101
Stephen Alstrup and
Thore Husfeldt and
Theis Rauhe and
Mikkel Thorup Black box for constant-time insertion in
priority queues (note) . . . . . . . . . 102--106
Doratha E. Drake Vinkemeier and
Stefan Hougardy A linear-time approximation algorithm
for weighted matchings in graphs . . . . 107--122
Peter J. Grabner and
Clemens Heuberger and
Helmut Prodinger and
Jörg M. Thuswaldner Analysis of linear combination
algorithms in cryptography . . . . . . . 123--142
Katarína Cechlárová and
Tamás Fleiner On a generalization of the stable
roommates problem . . . . . . . . . . . 143--156
Samir Khuller Problems column . . . . . . . . . . . . 157--159
David S. Johnson The NP-completeness column . . . . . . . 160--176
Svante Janson Individual displacements for linear
probing hashing with different insertion
policies . . . . . . . . . . . . . . . . 177--213
Alfredo Viola Exact distribution of individual
displacements in linear probing hashing 214--242
Stephen Alstrup and
Jacob Holm and
Mikkel Thorup and
Kristian De Lichtenberg Maintaining information in fully dynamic
trees with top trees . . . . . . . . . . 243--264
Raja Jothi and
Balaji Raghavachari Approximation algorithms for the
capacitated minimum spanning tree
problem and its variants in network
design . . . . . . . . . . . . . . . . . 265--282
Michael Elkin Computing almost shortest paths . . . . 283--323
Marcelo H. De Carvalho and
Joseph Cheriyan An $ O(V E) $ algorithm for ear
decompositions of matching-covered
graphs . . . . . . . . . . . . . . . . . 324--337
Ashish Goel and
Adam Meyerson and
Serge Plotkin Approximate majorization and fair online
load balancing . . . . . . . . . . . . . 338--349
Marek Chrobak and
Petr Kolman and
Ji\vrí Sgall The greedy algorithm for the minimum
common string partition problem . . . . 350--366
Joe Sawada Generating rooted and free plane trees 1--13
Rajneesh Hegde Finding $3$-shredders efficiently . . . 14--43
Jens Gramm and
Jiong Guo and
Rolf Niedermeier Pattern matching for arc-annotated
sequences . . . . . . . . . . . . . . . 44--65
Refael Hassin and
Asaf Levin The minimum generalized vertex cover
problem . . . . . . . . . . . . . . . . 66--78
Leah Epstein and
Rob Van Stee Online scheduling of splittable tasks 79--94
Teofilo F. Gonzalez and
Joseph Y.-T. Leung and
Michael Pinedo Minimizing total completion time on
uniform machines with deadline
constraints . . . . . . . . . . . . . . 95--115
Rajiv Gandhi and
Magnús M. Halldórsson and
Guy Kortsarz and
Hadas Shachnai Improved results for data migration and
open shop scheduling . . . . . . . . . . 116--129
Samir Khuller Problems column . . . . . . . . . . . . 130--134
James Korsh and
Paul Lafollette A loopless Gray code for rooted trees 135--152
Noga Alon and
Dana Moshkovitz and
Shmuel Safra Algorithmic construction of sets for
$k$-restrictions . . . . . . . . . . . . 153--177
Lap Chi Lau Bipartite roots of graphs . . . . . . . 178--208
Pankaj K. Agarwal and
Boris Aronov and
Vladlen Koltun Efficient algorithms for bichromatic
separability . . . . . . . . . . . . . . 209--227
Leah Epstein and
Rob Van Stee This side up! . . . . . . . . . . . . . 228--243
Yumei Huo and
Joseph Y.-T. Leung Minimizing mean flow time for UET tasks 244--262
Refael Hassin and
Danny Segev Robust subgraphs for trees and paths . . 263--281
Yossi Azar and
Yossi Richter An improved algorithm for CIOQ switches 282--295
Daniel Berend and
Amir Sapir The cyclic multi-peg Tower of Hanoi . . 297--317
Michael Drmota and
Helmut Prodinger The register function for $t$-ary trees 318--334
Lukasz Kowalik and
Maciej Kurowski Oracles for bounded-length shortest
paths in planar graphs . . . . . . . . . 335--363
Irit Katriel and
Hans L. Bodlaender Online topological ordering . . . . . . 364--379
Christian A. Duncan and
Stephen G. Kobourov and
V. S. Anil Kumar Optimal constrained graph exploration 380--402
Venkatesh Raman and
Saket Saurabh and
C. R. Subramanian Faster fixed parameter tractable
algorithms for finding feedback vertex
sets . . . . . . . . . . . . . . . . . . 403--415
Klaus Jansen and
Hu Zhang An approximation algorithm for
scheduling malleable tasks under general
precedence constraints . . . . . . . . . 416--434
Joan Feigenbaum and
Yuval Ishai and
Tal Malkin and
Kobbi Nissim and
Martin J. Strauss and
Rebecca N. Wright Secure multiparty computation of
approximations . . . . . . . . . . . . . 435--472
David S. Johnson The NP-completeness column: The many
limits on approximation . . . . . . . . 473--489
Alejandro López-Ortiz and
J. Ian Munro Foreword . . . . . . . . . . . . . . . . 491--491
David Eppstein Quasiconvex analysis of multivariate
recurrence equations for backtracking
algorithms . . . . . . . . . . . . . . . 492--509
Richard F. Geary and
Rajeev Raman and
Venkatesh Raman Succinct ordinal trees with
level-ancestor queries . . . . . . . . . 510--534
Ran Mendelson and
Robert E. Tarjan and
Mikkel Thorup and
Uri Zwick Melding priority queues . . . . . . . . 535--556
Surender Baswana and
Sandeep Sen Approximate distance oracles for
unweighted graphs in expected $ O(n^2) $
time . . . . . . . . . . . . . . . . . . 557--577
Camil Demetrescu and
Giuseppe F. Italiano Experimental analysis of dynamic all
pairs shortest path algorithms . . . . . 578--601
Robert W. Irving and
Telikepalli Kavitha and
Kurt Mehlhorn and
Dimitrios Michail and
Katarzyna E. Paluch Rank-maximal matchings . . . . . . . . . 602--610
Luca Foschini and
Roberto Grossi and
Ankur Gupta and
Jeffrey Scott Vitter When indexing equals compression:
Experiments with compressing suffix
arrays and applications . . . . . . . . 611--639
Noga Alon and
Baruch Awerbuch and
Yossi Azar and
Niv Buchbinder and
Joseph (Seffi) Naor A general approach to online network
optimization problems . . . . . . . . . 640--660
William Evans and
David Kirkpatrick Optimally scheduling video-on-demand to
minimize delay when sender and receiver
bandwidth may differ . . . . . . . . . . 661--678
Rene Beier and
Artur Czumaj and
Piotr Krysta and
Berthold Vöcking Computing equilibria for a service
provider game with (Im)perfect
information . . . . . . . . . . . . . . 679--706
Cristopher Moore and
Daniel Rockmore and
Alexander Russell Generic quantum Fourier transforms . . . 707--723
Aaron Archer and
Éva Tardos Frugal path mechanisms . . . . . . . . . ??
Randeep Bhatia and
Julia Chuzhoy and
Ari Freund and
Joseph (Seffi) Naor Algorithmic aspects of bandwidth trading ??
Renato Carmo and
Tomás Feder and
Yoshiharu Kohayakawa and
Eduardo Laber and
Rajeev Motwani and
Liadan O'Callaghan and
Rina Panigrahy and
Dilys Thomas Querying priced information in
databases: The conjunctive case . . . . ??
Valentina Ciriani and
Paolo Ferragina and
Fabrizio Luccio and
S. Muthukrishnan A data structure for a sequence of
string accesses in external memory . . . ??
Graham Cormode and
S. Muthukrishnan The string edit distance matching
problem with moves . . . . . . . . . . . ??
Artur Czumaj and
Berthold Vöcking Tight bounds for worst-case equilibria ??
Michael Elkin and
Guy Kortsarz An improved algorithm for radio
broadcast . . . . . . . . . . . . . . . ??
David Eppstein Foreword to special issue on SODA 2002 ??
John Hershberger and
Subhash Suri and
Amit Bhosle On the difficulty of some shortest path
problems . . . . . . . . . . . . . . . . ??
Gopal Pandurangan and
Eli Upfal Entropy-based bounds for online
algorithms . . . . . . . . . . . . . . . ??
Yevgen Voronenko and
Markus Püschel Multiplierless multiple constant
multiplication . . . . . . . . . . . . . 11:1--11:??
Hua-Huai Chern and
Michael Fuchs and
Hsien-Kuei Hwang Phase changes in random point quadtrees 12:1--12:??
Erik D. Demaine and
John Iacono and
Stefan Langerman Retroactive data structures . . . . . . 13:1--13:??
Ryan B. Hayward and
Jeremy P. Spinrad and
R. Sritharan Improved algorithms for weakly chordal
graphs . . . . . . . . . . . . . . . . . 14:1--14:??
Telikepalli Kavitha and
Kurt Mehlhorn and
Dimitrios Michail and
Katarzyna E. Paluch Strongly stable matchings in time $ O(n
m) $ and extension to the
hospitals-residents problem . . . . . . 15:1--15:??
Amitabha Bagchi and
Amitabh Chaudhary and
David Eppstein and
Michael T. Goodrich Deterministic sampling and range
counting in geometric data streams . . . 16:1--16:??
Sunil Arya and
Theocharis Malamatos and
David M. Mount A simple entropy-based algorithm for
planar point location . . . . . . . . . 17:1--17:17
Manuel Kauers An algorithm for deciding zero
equivalence of nested polynomially
recurrent sequences . . . . . . . . . . 18:1--18:??
Amihood Amir and
Gad M. Landau and
Moshe Lewenstein and
Dina Sokol Dynamic text and static pattern matching 19:1--19:??
Paolo Ferragina and
Giovanni Manzini and
Veli Mäkinen and
Gonzalo Navarro Compressed representations of sequences
and full-text indexes . . . . . . . . . 20:1--20:??
Ho-Leung Chan and
Wing-Kai Hon and
Tak-Wah Lam and
Kunihiko Sadakane Compressed indexes for dynamic text
collections . . . . . . . . . . . . . . 21:1--21:??
Joan Boyar and
Lene M. Favrholdt The relative worst order ratio for
online algorithms . . . . . . . . . . . 22:1--22:??
L. Becchetti and
J. Könemann and
S. Leonardi and
M. Páal Sharing the cost more efficiently:
Improved approximation for
multicommodity rent-or-buy . . . . . . . 23:1--23:??
David S. Johnson The NP-completeness column: Finding
needles in haystacks . . . . . . . . . . 24:1--24:??
Jianxing Feng and
Daming Zhu Faster algorithms for sorting by
transpositions and sorting by block
interchanges . . . . . . . . . . . . . . 25:1--25:14
Himanshu Gupta and
Rephael Wenger Constructing pairwise disjoint paths
with few links . . . . . . . . . . . . . 26:1--26:??
Chandra Chekuri and
Marcelo Mydlarz and
F. Bruce Shepherd Multicommodity demand flow in a tree and
packing integer programs . . . . . . . . 27:1--27:??
Amotz Bar-Noy and
Richard E. Ladner and
Tami Tamir Windows scheduling as a restricted
version of bin packing . . . . . . . . . 28:1--28:??
Carmit Hazay and
Moshe Lewenstein and
Dina Sokol Approximate parameterized matching . . . 29:1--29:??
Magnús M. Halldórsson and
Kazuo Iwama and
Shuichi Miyazaki and
Hiroki Yanagisawa Improved approximation results for the
stable marriage problem . . . . . . . . 30:1--30:??
Piotr Indyk and
Assaf Naor Nearest-neighbor-preserving embeddings 31:1--31:??
Eyal Even-Dar and
Alex Kesselman and
Yishay Mansour Convergence time to Nash equilibrium in
load balancing . . . . . . . . . . . . . 32:1--32:??
Matthew Andrews and
Lisa Zhang Routing and scheduling in multihop
wireless networks with time-varying
channels . . . . . . . . . . . . . . . . 33:1--33:??
Moni Naor and
Udi Wieder Novel architectures for P2P
applications: The continuous-discrete
approach . . . . . . . . . . . . . . . . 34:1--34:??
Samir Khuller Problems column . . . . . . . . . . . . 35:1--35:??
H. N. Gabow and
Michael A. Bender and
Martin Farach-Colton Introduction to SODA 2002 and 2003
special issue . . . . . . . . . . . . . 36:1--36:??
James Aspnes and
Gauri Shah Skip graphs . . . . . . . . . . . . . . 37:1--37:??
Yijie Han Optimal parallel selection . . . . . . . 38:1--38:??
Nikhil Bansal and
Kedar Dhamdhere Minimizing weighted flow time . . . . . 39:1--39:??
Jittat Fakcharoenphol and
Chris Harrelson and
Satish Rao The $k$-traveling repairmen problem . . 40:1--40:??
Sandy Irani and
Sandeep Shukla and
Rajesh Gupta Algorithms for power savings . . . . . . 41:1--41:??
Noga Alon and
Venkatesan Guruswami and
Tali Kaufman and
Madhu Sudan Guessing secrets efficiently via list
decoding . . . . . . . . . . . . . . . . 42:1--42:??
Rajeev Raman and
Venkatesh Raman and
Srinivasa Rao Satti Succinct indexable dictionaries with
applications to encoding $k$-ary trees,
prefix sums and multisets . . . . . . . 43:1--43:??
Svante Janson and
Wojciech Szpankowski Partial fillup and search time in LC
tries . . . . . . . . . . . . . . . . . 44:1--44:??
John Hershberger and
Matthew Maxel and
Subhash Suri Finding the $k$ shortest simple paths: a
new algorithm and its implementation . . 45:1--45:??
Chandra Chekuri and
Sanjeev Khanna Edge-disjoint paths revisited . . . . . 46:1--46:??
Joseph Cheriyan and
Mohammad R. Salavatipour Packing element-disjoint Steiner trees 47:1--47:??
Michael Krivelevich and
Zeev Nutov and
Mohammad R. Salavatipour and
Jacques Verstraete Yuster and
Raphael Yuster Approximation algorithms and hardness
results for cycle packing problems . . . 48:1--48:??
Susanne Albers and
Hiroshi Fujiwara Energy-efficient algorithms for flow
time minimization . . . . . . . . . . . 49:1--49:??
Marek Chrobak and
Wojciech Jawor and
Ji\vrí Sgall and
Tomá\vs Tichý Improved online algorithms for buffer
management in QoS switches . . . . . . . 50:1--50:??
Mohammad Taghi Hajiaghayi and
Robert D. Kleinberg and
Harald Räcke and
Tom Leighton Oblivious routing on node-capacitated
and directed graphs . . . . . . . . . . 51:1--51:??
Vincenzo Auletta and
Roberto De Prisco and
Paolo Penna and
Giuseppe Persiano Routing selfish unsplittable traffic . . 52:1--52:??
Milan Ru\vzi\'c Uniform deterministic dictionaries . . . 1:1--1:??
Gianni Franceschini and
Roberto Grossi No sorting? better searching! . . . . . 2:1--2:??
Haim Kaplan and
Robert Endre Tarjan Thin heaps, thick heaps . . . . . . . . 3:1--3:??
Jérémy Barbay and
Claire Kenyon Alternation and redundancy analysis of
the intersection problem . . . . . . . . 4:1--4:??
Seth Pettie and
Vijaya Ramachandran Randomized minimum spanning tree
algorithms using exponentially fewer
random bits . . . . . . . . . . . . . . 5:1--5:??
Liam Roditty A faster and simpler fully dynamic
transitive closure . . . . . . . . . . . 6:1--6:??
Harold N. Gabow and
Shuxin Nie Finding a long directed cycle . . . . . 7:1--7:??
Adam L. Buchsbaum and
Emden R. Gansner and
Cecilia M. Procopiuc and
Suresh Venkatasubramanian Rectangular layouts and contact graphs 8:1--8:??
Lars Arge and
Mark De Berg and
Herman Haverkort and
Ke Yi The priority R-tree: a practically
efficient and worst-case optimal R-tree 9:1--9:??
Joachim Gudmundsson and
Christos Levcopoulos and
Giri Narasimhan and
Michiel Smid Approximate distance oracles for
geometric spanners . . . . . . . . . . . 10:1--10:??
Rajiv Gandhi and
Magnús M. Halldórsson and
Guy Kortsarz and
Hadas Shachnai Improved bounds for scheduling
conflicting jobs with minsum criteria 11:1--11:??
Rachid Guerraoui and
Ron R. Levy and
Bastian Pochon and
Jim Pugh The collective memory of amnesic
processes . . . . . . . . . . . . . . . 12:1--12:??
George Karakostas Faster approximation schemes for
fractional multicommodity flow problems 13:1--13:17
Daniel Lemire and
Owen Kaser Hierarchical bin buffering: Online local
moments for dynamic external memory
arrays . . . . . . . . . . . . . . . . . 14:1--14:??
Elliot Anshelevich and
Lisa Zhang Path decomposition under a new cost
measure with applications to optical
network design . . . . . . . . . . . . . 15:1--15:??
Adam L. Buchsbaum Guest editorial . . . . . . . . . . . . 16:1--16:??
Daniel K. Blandford and
Guy E. Blelloch Compact dictionaries for variable-length
keys and data with applications . . . . 17:1--17:??
Ravikrishna Kolluri Provably good moving least squares . . . 18:1--18:??
Éric Fusy and
Gilles Schaeffer and
Dominique Poulalhon Dissections, orientations, and trees
with applications to optimal mesh
encoding and random sampling . . . . . . 19:1--19:??
László A. VéghVégh and
András A. Benczúr Primal-dual approach for directed vertex
connectivity augmentation and
generalizations . . . . . . . . . . . . 20:1--20:??
Peter Sanders and
David Steurer An asymptotic approximation scheme for
multigraph edge coloring . . . . . . . . 21:1--21:??
Shuchi Chawla and
Anupam Gupta and
Harald Räcke Embeddings of negative-type metrics and
an improved approximation to generalized
sparsest cut . . . . . . . . . . . . . . 22:1--22:??
Julia Chuzhoy and
Anupam Gupta and
Joseph (Seffi) Naor and
Amitabh Sinha On the approximability of some network
design problems . . . . . . . . . . . . 23:1--23:??
Nicole Immorlica and
Mohammad Mahdian and
Vahab S. Mirrokni Limitations of cross-monotonic
cost-sharing schemes . . . . . . . . . . 24:1--24:??
Yefim Dinitz and
Shay Solomon Optimality of an algorithm solving the
Bottleneck Tower of Hanoi problem . . . 25:1--25:??
Laurent Alonso and
Edward M. Reingold Determining plurality . . . . . . . . . 26:1--26:??
Laurent Alonso and
Edward M. Reingold Average-case lower bounds for the
plurality problem . . . . . . . . . . . 27:1--27:??
Hsueh-I Lu and
Chia-Chi Yeh Balanced parentheses strike back . . . . 28:1--28:??
Iam Roditty and
Mikkel Thorup and
Uri Zwick Roundtrip spanners and roundtrip routing
in directed graphs . . . . . . . . . . . 29:1--29:??
Qian-Ping Gu and
Hisao Tamaki Optimal branch-decomposition of planar
graphs in $ O(n^3) $ time . . . . . . . 30:1--30:??
Artur Czumaj and
Christian Sohler Testing Euclidean minimum spanning trees
in the plane . . . . . . . . . . . . . . 31:1--31:??
Veli Mäkinen and
Gonzalo Navarro Dynamic entropy-compressed sequences and
full-text indexes . . . . . . . . . . . 32:1--32:??
Dariusz R. Kowalski and
Alexander A. Shvartsman Writing-all deterministically and
optimally using a nontrivial number of
asynchronous processors . . . . . . . . 33:1--33:??
Guy Even and
Retsef Levi and
Dror Rawitz and
Baruch Schieber and
Shimon (Moni) Shahar and
Maxim Sviridenko Algorithms for capacitated rectangle
stabbing and lot sizing with joint
set-up costs . . . . . . . . . . . . . . 34:1--34:??
Cun-Quan Zhang and
Yongbin Ou Clustering, community partition and
disjoint spanning trees . . . . . . . . 35:1--35:??
Hung-I. Yu and
Tzu-Chin Lin and
Biing-Feng Wang Improved algorithms for the
minmax-regret 1-center and 1-median
problems . . . . . . . . . . . . . . . . 36:1--36:??
Ittai Abraham and
Cyril Gavoille and
Dahlia Malkhi and
Noam Nisan and
Mikkel Thorup Compact name-independent routing with
minimum stretch . . . . . . . . . . . . 37:1--37:??
Kirk Pruhs and
Patchrawat Uthaisombut and
Gerhard Woeginger Getting the best response for your erg 38:1--38:??
Deepak Ajwani and
Tobias Friedrich and
Ulrich Meyer An $ O(n^{2.75}) $ algorithm for
incremental topological ordering . . . . 39:1--39:??
Louis Ibarra Fully dynamic algorithms for chordal
graphs and split graphs . . . . . . . . 40:1--40:??
Amos Korman and
David Peleg Dynamic routing schemes for graphs with
low local density . . . . . . . . . . . 41:1--41:??
Reuven Cohen and
Pierre Fraigniaud and
David Ilcinkas and
Amos Korman and
David Peleg Label-guided graph exploration by a
finite automaton . . . . . . . . . . . . 42:1--42:??
Akiko Suzuki and
Takeshi Tokuyama Dense subgraph problems with
output-density conditions . . . . . . . 43:1--43:??
Amotz Bar-Noy and
Panagiotis Cheilaris and
Shakhar Smorodinsky Deterministic conflict-free coloring for
intervals: From offline to online . . . 44:1--44:18
Nishanth Chandran and
Ryan Moriarty and
Rafail Ostrovsky and
Omkant Pandey and
Mohammad Ali Safari and
Amit Sahai Improved algorithms for optimal
embeddings . . . . . . . . . . . . . . . 45:1--45:14
Noga Alon and
Mihai Bãdoiu and
Erik D. Demaine and
Martin Farach-Colton and
Mohammadtaghi Hajiaghayi and
Anastasios Sidiropoulos Ordinal embeddings of minimum
relaxation: General properties, trees,
and ultrametrics . . . . . . . . . . . . 46:1--46:??
Markus Bläser A new approximation algorithm for the
asymmetric TSP with triangle inequality 47:1--47:??
Joan Boyar and
Paul Medvedev The relative worst order ratio applied
to seat reservation . . . . . . . . . . 48:1--48:??
Tim Nieberg and
Johann Hurink and
Walter Kern Approximation schemes for wireless
networks . . . . . . . . . . . . . . . . 49:1--49:??
Jens Maßberg and
Jens Vygen Approximation algorithms for a facility
location problem with service capacities 50:1--50:15
Chaitanya Swamy and
David B. Shmoys Fault-tolerant facility location . . . . 51:1--51:??
Dimitris Fotakis and
Spyros Kontogiannis and
Paul Spirakis Atomic congestion games among coalitions 52:1--52:??
Eric Torng and
Jason McCullough SRPT optimally utilizes faster machines
to minimize flow time . . . . . . . . . 1:1--1:??
Michael H. Goldwasser and
Mark Pedigo Online nonpreemptive scheduling of
equal-length jobs on two identical
machines . . . . . . . . . . . . . . . . 2:1--2:18
William Aiello and
Alex Kesselman and
Yishay Mansour Competitive buffer management for
shared-memory switches . . . . . . . . . 3:1--3:??
Pankaj K. Agarwal and
Haim Kaplan and
Micha Sharir Kinetic and dynamic data structures for
closest pair and all nearest neighbors 4:1--4:??
Pankaj K. Agarwal and
Micha Sharir and
Emo Welzl Algorithms for center and Tverberg
points . . . . . . . . . . . . . . . . . 5:1--5:??
Fabrizio Grandoni and
Jochen Könemann and
Alessandro Panconesi Distributed weighted vertex cover via
maximal matchings . . . . . . . . . . . 6:1--6:12
Sundar Vishwanathan On hard instances of approximate vertex
cover . . . . . . . . . . . . . . . . . 7:1--7:??
Daniel Berend and
Steven S. Skiena and
Yochai Twitto Combinatorial dominance guarantees for
problems with infeasible solutions . . . 8:1--8:??
Fedor V. Fomin and
Fabrizio Grandoni and
Artem V. Pyatkin and
Alexey A. Stepanov Combinatorial bounds via measure and
conquer: Bounding minimal dominating
sets and applications . . . . . . . . . 9:1--9:??
Sang-Il Oum Approximating rank-width and
clique-width quickly . . . . . . . . . . 10:1--10:??
Andreas Brandstädt and
Van Bang Le and
R. Sritharan Structure and linear-time recognition of
4-leaf powers . . . . . . . . . . . . . 11:1--11:??
Xin Chen and
Lan Liu and
Zheng Liu and
Tao Jiang On the minimum common integer partition
problem . . . . . . . . . . . . . . . . 12:1--12:??
Dany Azriel and
Noam Solomon and
Shay Solomon On an infinite family of solvable Hanoi
graphs . . . . . . . . . . . . . . . . . 13:1--13:??
Amr Elmasry and
Claus Jensen and
Jyrki Katajainen Multipartite priority queues . . . . . . 14:1--14:??
David Eppstein Testing bipartiteness of geometric
intersection graphs . . . . . . . . . . 15:1--15:??
Ke Chen and
Haim Kaplan and
Micha Sharir Online conflict-free coloring for
halfplanes, congruent disks, and
axis-parallel rectangles . . . . . . . . 16:1--16:??
Laurent Alonso and
Edward M. Reingold Average-case analysis of some plurality
algorithms . . . . . . . . . . . . . . . 17:1--17:??
Amotz Bar-Noy and
Sudipto Guha and
Yoav Katz and
Joseph (Seffi) Naor and
Baruch Schieber and
Hadas Shachnai Throughput maximization of real-time
scheduling with batching . . . . . . . . 18:1--18:??
Yuval Rabani and
Gabriel Scalosub Bicriteria approximation tradeoff for
the node-cost budget problem . . . . . . 19:1--19:??
Guojun Li and
Xiaotie Deng and
Ying Xu A polynomial-time approximation scheme
for embedding hypergraph in a cycle . . 20:1--20:??
Guy Even and
Jon Feldman and
Guy Kortsarz and
Zeev Nutov A 1.8 approximation algorithm for
augmenting edge-connectivity of a graph
from 1 to 2 . . . . . . . . . . . . . . 21:1--21:??
Sharon Marko and
Dana Ron Approximating the distance to properties
in bounded-degree and general sparse
graphs . . . . . . . . . . . . . . . . . 22:1--22:??
Vincent Berry and
Christophe Paul and
Sylvain Guillemot and
François Nicolas Linear time 3-approximation for the MAST
problem . . . . . . . . . . . . . . . . 23:1--23:??
Anne Condon and
Amol Deshpande and
Lisa Hellerstein and
Ning Wu Algorithms for distributional and
adversarial pipelined filter ordering
problems . . . . . . . . . . . . . . . . 24:1--24:??
Harold Gabow Foreword to special issue on SODA 2007 25:1--25:??
Milan Ru\vzi\'c Making deterministic signatures quickly 26:1--26:??
Robert D. Carr and
Goran Konjevod and
Greg Little and
Venkatesh Natarajan and
Ojas Parekh Compacting cuts: a new linear
formulation for minimum cut . . . . . . 27:1--27:??
Yoav Giora and
Haim Kaplan Optimal dynamic vertical ray shooting in
rectilinear planar subdivisions . . . . 28:1--28:??
David Eppstein Squarepants in a tree: Sum of subtree
clustering and hyperbolic pants
decomposition . . . . . . . . . . . . . 29:1--29:??
Erik D. Demaine and
Mohammadtaghi Hajiaghayi and
Hamid Mahini and
Amin S. Sayedi-Roshkhar and
Shayan Oveisgharan and
Morteza Zadimoghaddam Minimizing movement . . . . . . . . . . 30:1--30:??
Glencora Borradaile and
Philip Klein and
Claire Mathieu An $ {O}(n \log n) $ approximation
scheme for Steiner tree in planar graphs 31:1--31:??
Glencora Borradaile and
Philip Klein and
Claire Mathieu An $ O(n \log n) $ approximation scheme
for Steiner tree in planar graphs . . . 31:1--31:??
Moses Charikar and
Konstantin Makarychev and
Yury Makarychev Near-optimal algorithms for maximum
constraint satisfaction problems . . . . 32:1--32:??
Matthew Andrews Instability of FIFO in the permanent
sessions model at arbitrarily small
network loads . . . . . . . . . . . . . 33:1--33:??
Leana Golubchik and
Sanjeev Khanna and
Samir Khuller and
Ramakrishna Thurimella and
An Zhu Approximation algorithms for data
placement on parallel disks . . . . . . 34:1--34:??
Sudipto Guha and
Andrew McGregor and
Suresh Venkatasubramanian Sublinear estimation of entropy and
information distances . . . . . . . . . 35:1--35:??
Asaf Levin A generalized minimum cost
$k$-clustering . . . . . . . . . . . . . 36:1--36:??
Martin Farach-Colton and
Rohan J. Fernandes and
Miguel A. Mosteiro Bootstrapping a hop-optimal network in
the weak sensor model . . . . . . . . . 37:1--37:??
David Eppstein All maximal independent sets and dynamic
dominance for sparse graphs . . . . . . 38:1--38:??
Bruce Reed and
David R. Wood A linear-time algorithm to find a
separator in a graph excluding a minor 39:1--39:??
Hiro Ito and
Kazuo Iwama Enumeration of isolated cliques and
pseudo-cliques . . . . . . . . . . . . . 40:1--40:??
George Karakostas A better approximation ratio for the
vertex cover problem . . . . . . . . . . 41:1--41:??
Daniel Berend and
Vladimir Braverman A linear algorithm for computing convex
hulls for random lines . . . . . . . . . 42:1--42:??
Ming-Yang Kao and
Manan Sanghi and
Robert Schweller Randomized fast design of short DNA
words . . . . . . . . . . . . . . . . . 43:1--43:??
David Fernández-Baca and
Balaji Venkatachalam Parametric analysis for ungapped Markov
models of evolution . . . . . . . . . . 44:1--44:??
Alexander D. Scott and
Gregory B. Sorkin Polynomial constraint satisfaction
problems, graph bisection, and the Ising
partition function . . . . . . . . . . . 45:1--45:??
Phong Q. Nguyen and
Damien Stehlé Low-dimensional lattice basis reduction
revisited . . . . . . . . . . . . . . . 46:1--46:??
Irene Finocchi and
Fabrizio Grandoni and
Giuseppe F. Italiano Resilient dictionaries . . . . . . . . . 1:1--1:??
Erik D. Demaine and
Shay Mozes and
Benjamin Rossman and
Oren Weimann An optimal decomposition algorithm for
tree edit distance . . . . . . . . . . . 2:1--2:??
Philip Bille and
Rolf Fagerberg and
Inge Li Gòrtz Improved approximate string matching and
regular expression matching on
Ziv--Lempel compressed texts . . . . . . 3:1--3:??
Amalia Duch and
Conrado Martínez Updating relaxed $ {K} $-d trees . . . . 4:1--4:??
Zeev Nutov Approximating connectivity augmentation
problems . . . . . . . . . . . . . . . . 5:1--5:19
Camil Demetrescu and
Irene Finocchi and
Andrea Ribichini Trading off space for passes in graph
streaming problems . . . . . . . . . . . 6:1--6:??
Seth Pettie Low distortion spanners . . . . . . . . 7:1--7:??
Kurt Mehlhorn and
Dimitrios Michail Minimum cycle bases: Faster and simpler 8:1--8:??
Serge Gaspers and
Dieter Kratsch and
Mathieu Liedloff and
Ioan Todinca Exponential time algorithms for the
minimum dominating set problem on some
graph classes . . . . . . . . . . . . . 9:1--9:??
Ho-Leung Chan and
Joseph Wun-Tat Chan and
Tak-Wah Lam and
Lap-Kei Lee and
Kin-Sum Mak and
Prudence W. H. Wong Optimizing throughput and energy in
online deadline scheduling . . . . . . . 10:1--10:??
Noga Alon and
Yossi Azar and
Shai Gutner Admission control to minimize rejections
and online set cover with repetitions 11:1--11:??
David Hay and
Gabriel Scalosub Jitter regulation for multiple streams 12:1--12:??
Luca Becchetti and
Alberto Marchetti-Spaccamela and
Andrea Vitaletti and
Peter Korteweg and
Martin Skutella and
Leen Stougie Latency-constrained aggregation in
sensor networks . . . . . . . . . . . . 13:1--13:??
Rami Cohen and
Dror Rawitz and
Danny Raz Time-dependent multi-scheduling of
multicast . . . . . . . . . . . . . . . 14:1--14:??
Iftah Gamzu and
Danny Segev Improved online algorithms for the
sorting buffer problem on line metrics 15:1--15:??
Konstantin Andreev and
Charles Garrod and
Daniel Golovin and
Bruce Maggs and
Adam Meyerson Simultaneous source location . . . . . . 16:1--16:??
Wolfgang Bein and
Mordecai J. Golin and
Lawrence L. Larmore and
Yan Zhang The Knuth--Yao quadrangle-inequality
speedup is a consequence of total
monotonicity . . . . . . . . . . . . . . 17:1--17:??
Refael Hassin and
Asaf Levin and
Maxim Sviridenko Approximating the minimum quadratic
assignment problems . . . . . . . . . . 18:1--18:??
Gorjan Alagic and
Cristopher Moore and
Alexander Russell Quantum algorithms for Simon's problem
over nonabelian groups . . . . . . . . . 19:1--19:??
László Babai and
Pedro F. Felzenszwalb Computing rank-convolutions with a mask 20:1--20:??
F. Thomas Bruss and
Guy Louchard and
Mark Daniel Ward Inverse auctions: Injecting unique
minima into random sets . . . . . . . . 21:1--21:??
Susanne Albers Editorial Note . . . . . . . . . . . . . 22:1--22:??
Claire Mathieu Foreword to special issue SODA 2009 . . 23:1--23:??
Sergio Cabello Finding shortest contractible and
shortest separating cycles in embedded
graphs . . . . . . . . . . . . . . . . . 24:1--24:??
James Aspnes and
Keren Censor Approximate shared-memory counting
despite a strong adversary . . . . . . . 25:1--25:??
Timothy M. Chan Comparison-based time-space lower bounds
for selection . . . . . . . . . . . . . 26:1--26:??
Ashish Goel and
Michael Kapralov and
Sanjeev Khanna Perfect matchings via uniform sampling
in regular bipartite graphs . . . . . . 27:1--27:??
Benjamin Aminof and
Orna Kupferman and
Robby Lampert Reasoning about online algorithms with
weighted automata . . . . . . . . . . . 28:1--28:??
Dániel Marx Approximating fractional hypertree width 29:1--29:??
Philip N. Klein and
Shay Mozes and
Oren Weimann Shortest paths in directed planar graphs
with negative lengths: a linear-space $
O(n \log^2 n) $-time algorithm . . . . . 30:1--30:??
Konstantinos Panagiotou and
Angelika Steger Maximal biconnected subgraphs of random
planar graphs . . . . . . . . . . . . . 31:1--31:??
Stéphan Thomassé A $ 4 k^2 $ kernel for feedback vertex
set . . . . . . . . . . . . . . . . . . 32:1--32:??
Stéphan Thomassé A $ 4 k^2 $ kernel for feedback vertex
set . . . . . . . . . . . . . . . . . . 32:1--32:??
Omid Madani and
Mikkel Thorup and
Uri Zwick Discounted deterministic Markov decision
processes and discounted all-pairs
shortest paths . . . . . . . . . . . . . 33:1--33:??
Alon Shalita and
Uri Zwick Efficient algorithms for the 2-gathering
problem . . . . . . . . . . . . . . . . 34:1--34:??
Nikhil Bansal and
Ning Chen and
Neva Cherniavsky and
Atri Rurda and
Baruch Schieber and
Maxim Sviridenko Dynamic pricing for impatient bidders 35:1--35:??
Yossi Azar and
Iftah Gamzu and
Shai Gutner Truthful unsplittable flow for large
capacity networks . . . . . . . . . . . 36:1--36:??
Zoya Svitkina and
Éva Tardos Facility location with hierarchical
facility costs . . . . . . . . . . . . . 37:1--37:??
George Christodoulou and
Elias Koutsoupias and
Annamária Kovács Mechanism design for fractional
scheduling on unrelated machines . . . . 38:1--38:??
Amos Korman Labeling schemes for vertex connectivity 39:1--39:??
Ayelet Butman and
Danny Hermelin and
Moshe Lewenstein and
Dror Rawitz Optimization problems in
multiple-interval graphs . . . . . . . . 40:1--40:??
Anupam Gupta and
Mohammadtaghi Hajiaghayi and
Viswanath Nagarajan and
R. Ravi Dial a Ride from $k$-forest . . . . . . 41:1--41:??
Anupam Gupta and
Mohammadtaghi Hajiaghayi and
Viswanath Nagarajan and
R. Ravi Dial a Ride from $k$-forest . . . . . . 41:1--41:??
Bruce Bobier and
Joe Sawada A fast algorithm to generate open
meandric systems and meanders . . . . . 42:1--42:??
Funda Ergun and
S. Muthukrishnan and
Cenk Sahinalp Periodicity testing with sublinear
samples and space . . . . . . . . . . . 43:1--43:??
Virginia Vassilevska and
Ryan Williams and
Raphael Yuster Finding heaviest $H$-subgraphs in real
weighted graphs, with applications . . . 44:1--44:??
Frank Ruskey and
Aaron Williams An explicit universal cycle for the $ (n
- 1) $-permutations of an $n$-set . . . 45:1--45:12
Matthew Drescher and
Adrian Vetta An approximation algorithm for the
maximum leaf spanning arborescence
problem . . . . . . . . . . . . . . . . 46:1--46:??
Joseph (Seffi) Naor and
Roy Schwartz The directed circular arrangement
problem . . . . . . . . . . . . . . . . 47:1--47:??
Yossi Azar and
Shay Kutten and
Boaz Patt-Shamir Distributed error confinement . . . . . 48:1--48:??
Gagan Aggarwal and
Rina Panigrahy and
Tomás Feder and
Dilys Thomas and
Krishnaram Kenthapadi and
Samir Khuller and
An Zhu Achieving anonymity via clustering . . . 49:1--49:??
Eyal Gordon and
Adi Rosén Competitive weighted throughput analysis
of greedy protocols on DAGs . . . . . . 50:1--50:??
Amit Chakrabarti and
Graham Cormode and
Andrew Mcgregor A near-optimal algorithm for estimating
the entropy of a stream . . . . . . . . 51:1--51:??
Shahar Fattal and
Dana Ron Approximating the distance to
monotonicity in high dimensions . . . . 52:1--52:??
Conrado Martínez and
Daniel Panario and
Alfredo Viola Adaptive sampling strategies for
quickselects . . . . . . . . . . . . . . 53:1--53:??
Noga Alon and
Shai Gutner Balanced families of perfect hash
functions and their applications . . . . 54:1--54:??
Don Coppersmith and
Lisa K. Fleischer and
Atri Rurda Ordering by weighted number of wins
gives a good ranking for weighted
tournaments . . . . . . . . . . . . . . 55:1--55:??
Arturo Gonzalez-Gutierrez and
Teofilo F. Gonzalez Approximating corridors and tours via
restriction and relaxation techniques 56:1--56:??
Susanne Alber Editorial note . . . . . . . . . . . . . 57:1--57:??
Mohammad T. Hajiaghayi and
Shang-Hua Teng Foreword to special issue on SODA 2008 58:1--58:??
Marcel R. Ackermann and
Johannes Blömer and
Christian Sohler Clustering for metric and nonmetric
distance measures . . . . . . . . . . . 59:1--59:??
Reid Andersen A local algorithm for finding dense
subgraphs . . . . . . . . . . . . . . . 60:1--60:??
Sergio Cabello and
Matt Devos and
Jeff Erickson and
Bojan Mohar Finding one tight cycle . . . . . . . . 61:1--61:??
Timothy M. Chan On the bichromatic $k$-set problem . . . 62:1--62:??
Kenneth L. Clarkson Coresets, sparse greedy approximation,
and the Frank--Wolfe algorithm . . . . . 63:1--63:??
Yuval Emek and
David Peleg and
Liam Roditty A near-linear-time algorithm for
computing replacement paths in planar
directed graphs . . . . . . . . . . . . 64:1--64:??
Ulrich Faigle and
Britta Peis Two-phase greedy algorithms for some
classes of combinatorial linear programs 65:1--65:??
Jon Feldman and
S. Muthukrishnan and
Anastasios Sidiropoulos and
Cliff Stein and
Zoya Svitkina On distributing symmetric streaming
computations . . . . . . . . . . . . . . 66:1--66:??
Steve Y. Oudot and
Leonidas J. Guibas and
Jie Gao and
Yue Wang Geodesic Delaunay triangulations in
bounded planar domains . . . . . . . . . 67:1--67:??
Bruce M. Kapron and
David Kempe and
Valerie King and
Jared Saia and
Vishal Sanwalani Fast asynchronous Byzantine agreement
and leader election with full
information . . . . . . . . . . . . . . 68:1--68:??
Zoya Svitkina Lower-bounded facility location . . . . 69:1--69:??
Virginia Vassilevska Williams Nondecreasing paths in a weighted graph
or: How to optimally read a train
schedule . . . . . . . . . . . . . . . . 70:1--70:??
Pankaj K. Agarwal and
Sariel Har-Peled and
Micha Sharir and
Yusu Wang Hausdorff distance under translation for
points and balls . . . . . . . . . . . . 71:1--71:??
John Gunnar Carlsson and
Benjamin Armbruster and
Yinyu Ye Finding equitable convex partitions of
points in a polygon efficiently . . . . 72:1--72:??
Ignaz Rutter and
Alexander Wolff Computing large matchings fast . . . . . 1:1--1:??
Kazuo Iwama and
Shuichi Miyazaki and
Hiroki Yanagisawa Approximation algorithms for the
sex-equal stable marriage problem . . . 2:1--2:??
Hristo N. Djidjev A faster algorithm for computing the
girth of planar and bounded genus graphs 3:1--3:??
Georg Baier and
Thomas Erlebach and
Alexander Hall and
Ekkehard Köhler and
Petr Kolman and
Ondrej Pangrác and
Heiko Schilling and
Martin Skutella Length-bounded cuts and flows . . . . . 4:1--4:??
Surender Baswana and
Telikepalli Kavitha and
Kurt Mehlhorn and
Seth Pettie Additive spanners and $ (\alpha,
\beta)$-spanners . . . . . . . . . . . . 5:1--5:??
Michele Flammini and
Gaia Nicosia On the bicriteria $k$-server problem . . 6:1--6:??
Leah Epstein and
Rob Van Stee On the online unit clustering problem 7:1--7:??
Jie Gao and
Michael Langberg and
Leonard J. Schulman Clustering lines in high-dimensional
space: Classification of incomplete data 8:1--8:??
Atlas F. Cook IV and
Carola Wenk Geodesic Fréchet distance inside a simple
polygon . . . . . . . . . . . . . . . . 9:1--9:??
Paolo Ferragina and
Rossano Venturini The compressed permuterm index . . . . . 10:1--10:??
Pankaj K. Agarwal and
Lars Arge and
Ke Yi I/O-efficient batched union--find and
its applications to terrain analysis . . 11:1--11:??
Ashish Goel and
Sudipto Guha and
Kamesh Munagala How to probe for an extreme value . . . 12:1--12:??
Ioannis Caragiannis and
Christos Kaklamanis and
Panagiotis Kanellopoulos Taxes for linear atomic congestion games 13:1--13:??
Loukas Georgiadis and
Haim Kaplan and
Nira Shafrir and
Robert E. Tarjan and
Renato F. Werneck Data structures for mergeable trees . . 14:1--14:??
Venkatesan T. Chakaravarthy and
Vinayaka Pandit and
Sambuddha Roy and
Pranjal Awasthi and
Mukesh K. Mohania Decision trees for entity
identification: Approximation algorithms
and hardness results . . . . . . . . . . 15:1--15:??
Tobias Jacobs Constant factor approximations for the
hotlink assignment problem . . . . . . . 16:1--16:??
Christoph Ambühl and
Leszek Gasieniec and
Andrzej Pelc and
Tomasz Radzik and
Xiaohui Zhang Tree exploration with logarithmic memory 17:1--17:??
Chandra Chekuri and
Guy Even and
Anupam Gupta and
Danny Segev Set connectivity problems in undirected
graphs and the directed Steiner network
problem . . . . . . . . . . . . . . . . 18:1--18:??
Éric Colin De Verdi\`ere and
Alexander Schrijver Shortest vertex-disjoint two-face paths
in planar graphs . . . . . . . . . . . . 19:1--19:??
Michael Elkin Streaming and fully dynamic centralized
algorithms for constructing and
maintaining sparse spanners . . . . . . 20:1--20:??
Graham Cormode and
S. Muthukrishnan and
Ke Yi Algorithms for distributed functional
monitoring . . . . . . . . . . . . . . . 21:1--21:??
Magnús M. Halldórsson and
Guy Kortsarz and
Maxim Sviridenko Sum edge coloring of multigraphs via
configuration LP . . . . . . . . . . . . 22:1--22:21
Avraham Ben-Aroya and
Sivan Toledo Competitive analysis of flash memory
algorithms . . . . . . . . . . . . . . . 23:1--23:??
Yonatan Aumann and
Moshe Lewenstein and
Noa Lewenstein and
Dekel Tsur Finding witnesses by peeling . . . . . . 24:1--24:??
Yongwook Choi and
Wojciech Szpankowski Constrained pattern matching . . . . . . 25:1--25:??
Bin Fu and
Ming-Yang Kao and
Lusheng Wang Discovering almost any hidden motif from
multiple sequences . . . . . . . . . . . 26:1--26:??
Ge Nong and
Sen Zhang and
Wai Hong Chan Computing the Inverse Sort Transform in
linear time . . . . . . . . . . . . . . 27:1--27:??
Zachary Friggstad and
Mohammad R. Salavatipour Minimizing movement in mobile facility
location problems . . . . . . . . . . . 28:1--28:??
Allan Borodin and
David Cashman and
Avner Magen How well can primal-dual and local-ratio
algorithms perform? . . . . . . . . . . 29:1--29:??
Kai-Min Chung and
Omer Reingold and
Salil Vadhan S-T connectivity on digraphs with a
known stationary distribution . . . . . 30:1--30:??
Martin Gairing and
Burkhard Monien and
Karsten Tiemann Routing (un-) splittable flow in games
with player-specific affine latency
functions . . . . . . . . . . . . . . . 31:1--31:??
Adi Rosén and
Gabriel Scalosub Rate vs. buffer size --- greedy
information gathering on the line . . . 32:1--32:??
Vincenzo Bonifaci and
Peter Korteweg and
Alberto Marchetti-Spaccamela and
Leen Stougie Minimizing flow time in the wireless
gathering problem . . . . . . . . . . . 33:1--33:??
Evangelos Kranakis and
Danny Krizanc and
Pat Morin Randomized rendezvous with limited
memory . . . . . . . . . . . . . . . . . 34:1--34:??
Sriram V. Pemmaraju and
Rajiv Raman and
Kasturi Varadarajan Max-coloring and online coloring with
bandwidths on interval graphs . . . . . 35:1--35:??
Samir Khuller and
Azarakhsh Malekian and
Julián Mestre To fill or not to fill: The gas station
problem . . . . . . . . . . . . . . . . 36:1--36:??
Don Coppersmith and
Tomasz Nowicki and
Giuseppe Paleologo and
Charles Tresser and
Chai Wah Wu The optimality of the online greedy
algorithm in carpool and chairman
assignment problems . . . . . . . . . . 37:1--37:??
Philip Bille and
Inge Li Gortz The tree inclusion problem: In linear
space and faster . . . . . . . . . . . . 38:1--38:47
Eduardo Laber and
Marco Molinaro Improved approximations for the hotlink
assignment problem . . . . . . . . . . . 39:1--39:??
Bruno Salvy and
Bob Sedgewick and
Michele Soria and
Wojciech Szpankowski and
Brigitte Vallee Philippe Flajolet, the father of
analytic combinatorics . . . . . . . . . 40:1--40:??
Zdenek Dvorák and
Ken-Ichi Kawarabayashi and
Robin Thomas Three-coloring triangle-free planar
graphs in linear time . . . . . . . . . 41:1--41:??
Shlomo Moran and
Sagi Snir and
Wing-Kin Sung Partial convex recolorings of trees and
galled networks: Tight upper and lower
bounds . . . . . . . . . . . . . . . . . 42:1--42:??
Sergio Cabello and
Panos Giannopoulos and
Christian Knauer and
Dániel Marx and
Günter Rote Geometric clustering: Fixed-parameter
tractability and lower bounds with
respect to the dimension . . . . . . . . 43:1--43:??
Paul Bonsma and
Frederic Dorn Tight bounds and a fast FPT algorithm
for directed Max-Leaf Spanning Tree . . 44:1--44:??
Liam Roditty and
Asaf Shapira All-pairs shortest paths with a
sublinear additive error . . . . . . . . 45:1--45:??
David Pritchard and
Ramakrishna Thurimella Fast computation of small cuts via cycle
space sampling . . . . . . . . . . . . . 46:1--46:??
Jessica Chang and
Thomas Erlebach and
Renars Gailis and
Samir Khuller Broadcast scheduling: Algorithms and
complexity . . . . . . . . . . . . . . . 47:1--47:??
Gruia Calinescu and
Amit Chakrabarti and
Howard Karloff and
Yuval Rabani An improved approximation algorithm for
resource allocation . . . . . . . . . . 48:1--48:??
Dimitris Fotakis Memoryless facility location in one pass 49:1--49:??
Xin Han and
Francis Y. L. Chin and
Hing-Fung Ting and
Guochuan Zhang and
Yong Zhang A new upper bound $ 2.5545 $ on $2$D
Online Bin Packing . . . . . . . . . . . 50:1--50:??
Jeff Edmonds and
Kirk Pruhs Cake cutting really is not a piece of
cake . . . . . . . . . . . . . . . . . . 51:1--51:??
Jérémy Barbay and
Meng He and
J. Ian Munro and
Srinivasa Rao Satti Succinct indexes for strings, binary
relations and multilabeled trees . . . . 52:1--52:??
Luís M. S. Russo and
Gonzalo Navarro and
Arlindo L. Oliveira Fully compressed suffix trees . . . . . 53:1--53:??
Alexander Izsak and
Nicholas Pippenger Carry propagation in multiplication by
constants . . . . . . . . . . . . . . . 54:1--54:??
Sudipto Guha and
Kamesh Munagala Adaptive Uncertainty Resolution in
Bayesian Combinatorial Optimization
Problems . . . . . . . . . . . . . . . . 1:1--1:??
Mohammad Mahdian and
Hamid Nazerzadeh and
Amin Saberi Online Optimization with Uncertain
Information . . . . . . . . . . . . . . 2:1--2:??
Bernhard Haeupler and
Telikepalli Kavitha and
Rogers Mathew and
Siddhartha Sen and
Robert E. Tarjan Incremental Cycle Detection, Topological
Ordering, and Strong Component
Maintenance . . . . . . . . . . . . . . 3:1--3:??
Matteo Frigo and
Charles E. Leiserson and
Harald Prokop and
Sridhar Ramachandran Cache-Oblivious Algorithms . . . . . . . 4:1--4:??
Bogdan S. Chlebus and
Dariusz R. Kowalski and
Mariusz A. Rokicki Adversarial Queuing on the Multiple
Access Channel . . . . . . . . . . . . . 5:1--5:??
Jianer Chen and
Yang Liu and
Songjian Lu and
Sing-Hoi Sze and
Fenghui Zhang Iterative Expansion and Color Coding: An
Improved Algorithm for $3$D-Matching . . 6:1--6:??
Sebastian Böcker and
Quang Bao Anh Bui and
Anke Truss Improved Fixed-Parameter Algorithms for
Minimum-Flip Consensus Trees . . . . . . 7:1--7:??
Marek Cygan and
Marcin Pilipczuk Even Faster Exact Bandwidth . . . . . . 8:1--8:??
Yonatan Aumann and
Moshe Lewenstein and
Oren Melamud and
Ron Pinter and
Zohar Yakhini Dotted interval graphs . . . . . . . . . 9:1--9:??
Prosenjit Bose and
Eric Y. Chen and
Meng He and
Anil Maheshwari and
Pat Morin Succinct geometric indexes supporting
point location queries . . . . . . . . . 10:1--10:??
Michael Drmota and
Reinhard Kutzelnigg A precise analysis of Cuckoo hashing . . 11:1--11:36
Ke Yi and
Qin Zhang Multidimensional online tracking . . . . 12:1--12:??
Erik D. Demaine and
Mohammadtaghi Hajiaghayi and
Hamid Mahini and
Morteza Zadimoghaddam The price of anarchy in network creation
games . . . . . . . . . . . . . . . . . 13:1--13:??
Yuli Ye and
Allan Borodin Elimination graphs . . . . . . . . . . . 14:1--14:??
Eldar Fischer and
Oded Lachish and
Arie Matsliah and
Ilan Newman and
Orly Yahalom On the query complexity of testing
orientations for being Eulerian . . . . 15:1--15:??
Toshihiro Fujito How to trim a MST: a $2$-approximation
algorithm for minimum cost-tree cover 16:1--16:??
Bodo Manthey On approximating multicriteria TSP . . . 17:1--17:??
Andreas Björklund and
Thore Husfeldt and
Petteri Kaski and
Mikko Koivisto The traveling salesman problem in
bounded degree graphs . . . . . . . . . 18:1--18:??
Andrei Krokhin and
Dániel Marx On the hardness of losing weight . . . . 19:1--19:??
Mohammadhossein Bateni and
Mohammadtaghi Hajiaghayi Assignment problem in content
distribution networks: Unsplittable
hard-capacitated facility location . . . 20:1--20:??
Alessandro Panconesi and
Jaikumar Radhakrishnan Expansion properties of (secure)
wireless networks . . . . . . . . . . . 21:1--21:??
Ulrich Meyer and
Norbert Zeh I/O-efficient shortest path algorithms
for undirected graphs with random or
bounded edge lengths . . . . . . . . . . 22:1--22:??
Chandra Chekuri and
Nitish Korula and
Martin Pál Improved algorithms for orienteering and
related problems . . . . . . . . . . . . 23:1--23:??
Arash Asadpour and
Uriel Feige and
Amin Saberi Santa Claus meets hypergraph matchings 24:1--24:??
Angelo Fanelli and
Michele Flammini and
Luca Moscardelli The speed of convergence in congestion
games under best-response dynamics . . . 25:1--25:??
Philippe Baptiste and
Marek Chrobak and
Christoph Dürr Polynomial-time algorithms for minimum
energy scheduling . . . . . . . . . . . 26:1--26:??
Florian Diedrich and
Klaus Jansen and
Lars Prädel and
Ulrich M. Schwarz and
Ola Svensson Tight approximation algorithms for
scheduling with fixed jobs and
nonavailability . . . . . . . . . . . . 27:1--27:??
Jeff Edmonds and
Kirk Pruhs Scalably scheduling processes with
arbitrary speedup curves . . . . . . . . 28:1--28:??
Sébastien Collette and
Vida Dujmovi\'c and
John Iacono and
Stefan Langerman and
Pat Morin Entropy, triangulation, and point
location in planar subdivisions . . . . 29:1--29:??
Valentina Damerow and
Bodo Manthey and
Friedhelm Meyer Auf Der Heide and
Harald Räcke and
Christian Scheideler and
Christian Sohler and
Till Tantau Smoothed analysis of left-to-right
maxima with applications . . . . . . . . 30:1--30:??
Frédérique Bassino and
Julien Clément and
Pierre Nicod\`eme Counting occurrences for a finite set of
words: combinatorial methods . . . . . . 31:1--31:??
V. Arvind and
Piyush P. Kurur Testing nilpotence of Galois groups in
polynomial time . . . . . . . . . . . . 32:1--32:??
Liam Roditty and
Uri Zwick Replacement paths and $k$ simple
shortest paths in unweighted directed
graphs . . . . . . . . . . . . . . . . . 33:1--33:??
Timothy M. Chan All-pairs shortest paths for unweighted
undirected graphs in $ o(m n) $ time . . 34:1--34:??
Surender Baswana and
Sumeet Khurana and
Soumojit Sarkar Fully dynamic randomized algorithms for
graph spanners . . . . . . . . . . . . . 35:1--35:??
Chaitanya Swamy The effectiveness of Stackelberg
strategies and tolls for network
congestion games . . . . . . . . . . . . 36:1--36:??
Jurek Czyzowicz and
Andrzej Pelc and
Arnaud Labourel How to meet asynchronously (almost)
everywhere . . . . . . . . . . . . . . . 37:1--37:??
Daniel Binkele-Raible and
Henning Fernau and
Fedor V. Fomin and
Daniel Lokshtanov and
Saket Saurabh and
Yngve Villanger Kernel(s) for problems with no kernel:
On out-trees with many leaves . . . . . 38:1--38:??
Sungjin Im and
Benjamin Moseley An online scalable algorithm for average
flow time in broadcast scheduling . . . 39:1--39:??
George Karakostas and
Stavros G. Kolliopoulos and
Jing Wang An FPTAS for the minimum total weighted
tardiness problem with a fixed number of
distinct due dates . . . . . . . . . . . 40:1--40:??
Amol Deshpande and
Lisa Hellerstein Parallel pipelined filter ordering with
precedence constraints . . . . . . . . . 41:1--41:??
Meng He and
J. Ian Munro and
Srinivasa Rao Satti Succinct ordinal trees based on tree
covering . . . . . . . . . . . . . . . . 42:1--42:??
Pankaj K. Agarwal and
Siu-Wing Cheng and
Ke Yi Range searching on uncertain data . . . 43:1--43:??
Alexandr Andoni and
Robert Krauthgamer The smoothed complexity of edit distance 44:1--44:??
Zeev Nutov Approximating minimum-cost connectivity
problems via uncrossable bifamilies . . 1:1--1:??
Mohammadtaghi Hajiaghayi and
Rohit Khandekar and
Guy Kortsarz and
Zeev Nutov Prize-collecting Steiner network
problems . . . . . . . . . . . . . . . . 2:1--2:??
Baruch Awerbuch and
Rohit Khandekar and
Satish Rao Distributed algorithms for
multicommodity flow problems via
approximate steepest descent framework 3:1--3:??
Wei Chen and
Christian Sommer and
Shang-Hua Teng and
Yajun Wang A compact routing scheme and approximate
distance oracle for power-law graphs . . 4:1--4:??
Lukasz Jez and
Fei Li and
Jay Sethuraman and
Clifford Stein Online scheduling of packets with
agreeable deadlines . . . . . . . . . . 5:1--5:??
Vincenzo Bonifaci and
Ho-Leung Chan and
Alberto Marchetti-Spaccamela and
Nicole Megow Algorithms and complexity for periodic
real-time scheduling . . . . . . . . . . 6:1--6:??
Magnús M. Halldórsson Wireless scheduling with power control 7:1--7:??
Javad B. Ebrahimi and
Christina Fragouli Combinatiorial algorithms for wireless
information flow . . . . . . . . . . . . 8:1--8:??
Chandra Chekuri and
Kenneth L. Clarkson and
Sariel Har-Peled On the set multicover problem in
geometric settings . . . . . . . . . . . 9:1--9:??
Joachim Giesen and
Martin Jaggi and
Sören Laue Approximating parameterized convex
optimization problems . . . . . . . . . 10:1--10:??
Geevarghese Philip and
Venkatesh Raman and
Somnath Sikdar Polynomial kernels for dominating set in
graphs of bounded degeneracy and beyond 11:1--11:??
Hans L. Bodlaender and
Fedor V. Fomin and
Arie M. C. A. Koster and
Dieter Kratsch and
Dimitrios M. Thilikos On exact algorithms for treewidth . . . 12:1--12:??
Amihood Amir and
Estrella Eisenberg and
Avivit Levy and
Ely Porat and
Natalie Shapira Cycle detection and correction . . . . . 13:1--13:??
Oren Weimann and
Raphael Yuster Replacement Paths and Distance
Sensitivity Oracles via Fast Matrix
Multiplication . . . . . . . . . . . . . 14:1--14:??
Liam Roditty and
Roei Tov Approximating the Girth . . . . . . . . 15:1--15:??
Ken-Ichi Kawarabayashi and
Yusuke Kobayashi An $ O(\log n) $-Approximation Algorithm
for the Edge-Disjoint Paths Problem in
Eulerian Planar Graphs . . . . . . . . . 16:1--16:??
Pierre Fraigniaud and
Andrzej Pelc Delays Induce an Exponential Memory Gap
for Rendezvous in Trees . . . . . . . . 17:1--17:??
Nikhil Bansal and
Ho-Leung Chan and
Kirk Pruhs Speed Scaling with an Arbitrary Power
Function . . . . . . . . . . . . . . . . 18:1--18:??
Dorit S. Hochbaum and
Asaf Levin Approximation Algorithms for a
Minimization Variant of the
Order-Preserving Submatrices and for
Biclustering Problems . . . . . . . . . 19:1--19:??
Shuchi Chawla and
Prasad Raghavendra and
Dana Randall Foreword to the Special Issue on SODA'11 20:1--20:??
Nir Ailon and
Edo Liberty An Almost Optimal Unrestricted Fast
Johnson--Lindenstrauss Transform . . . . 21:1--21:??
Timothy M. Chan Persistent Predecessor Search and
Orthogonal Point Location on the Word
RAM . . . . . . . . . . . . . . . . . . 22:1--22:??
Constantinos Daskalakis On the Complexity of Approximating a
Nash Equilibrium . . . . . . . . . . . . 23:1--23:??
Friedrich Eisenbrand and
Dömötör Pálvölgyi and
Thomas Rothvoß Bin Packing via Discrepancy of
Permutations . . . . . . . . . . . . . . 24:1--24:??
Pawel Gawrychowski Optimal Pattern Matching in LZW
Compressed Strings . . . . . . . . . . . 25:1--25:??
T. S. Jayram and
David P. Woodruff Optimal Bounds for
Johnson--Lindenstrauss Transforms and
Streaming Problems with Subconstant
Error . . . . . . . . . . . . . . . . . 26:1--26:??
Jakub Lacki Improved Deterministic Algorithms for
Decremental Reachability and Strongly
Connected Components . . . . . . . . . . 27:1--27:??
Shay Solomon Sparse Euclidean Spanners with Tiny
Diameter . . . . . . . . . . . . . . . . 28:1--28:??
Therese Biedl and
Anna Lubiw and
Mark Petrick and
Michael Spriggs Morphing orthogonal planar graph
drawings . . . . . . . . . . . . . . . . 29:1--29:??
Dáaniel Marx and
Barry O'Sullivan and
Igor Razgon Finding small separators in linear time
via treewidth reduction . . . . . . . . 30:1--30:??
Christoph Ambühl and
Bernd Gärtner and
Bernhard von Stengel Optimal lower bounds for projective list
update algorithms . . . . . . . . . . . 31:1--31:??
Mohammadhossein Bateni and
Mohammadtaghi Hajiaghayi and
Morteza Zadimoghaddam Submodular secretary problem and
extensions . . . . . . . . . . . . . . . 32:1--32:??
Erich Kaltofen and
George Yuhasz On the matrix Berlekamp--Massey
algorithm . . . . . . . . . . . . . . . 33:1--33:??
Rajiv Gandhi and
Magnús M. Halldórsson and
Guy Kortsarz and
Hadas Shachnai Corrigendum: Improved results for data
migration and open shop scheduling . . . 34:1--34:??
Nikhil Bansal and
Zachary Friggstad and
Rohit Khandekar and
Mohammad R. Salavatipour A logarithmic approximation for
unsplittable flow on line graphs . . . . 1:1--1:??
Julián Mestre Weighted popular matchings . . . . . . . 2:1--2:??
Sariel Har-Peled and
Benjamin Raichel The Fréchet distance revisited and
extended . . . . . . . . . . . . . . . . 3:1--3:??
Antoine Vigneron Geometric optimization and sums of
algebraic functions . . . . . . . . . . 4:1--4:??
Ashish Goel and
Hamid Nazerzadeh Price-based protocols for fair resource
allocation: Convergence time analysis
and extension to Leontief utilities . . 5:1--5:??
Juanjo Rué and
Ignasi Sau and
Dimitrios M. Thilikos Dynamic programming for graphs on
surfaces . . . . . . . . . . . . . . . . 8:1--8:??
Susanne Albers and
Antonios Antoniadis Race to idle: New algorithms for speed
scaling with a sleep state . . . . . . . 9:1--9:??
Ho Yee Cheung and
Lap Chi Lau and
Kai Man Leung Algebraic Algorithms for Linear Matroid
Parity Problems . . . . . . . . . . . . 10:1--10:??
Joan Feigenbaum and
Aaron D. Jaggard and
Michael Schapira Approximate Privacy: Foundations and
Quantification . . . . . . . . . . . . . 11:1--11:??
Amnon Ta-Shma and
Uri Zwick Deterministic Rendezvous, Treasure
Hunts, and Strongly Universal
Exploration Sequences . . . . . . . . . 12:1--12:??
Erik D. Demaine and
Mohammadtaghi Hajiaghayi and
Philip N. Klein Node-Weighted Steiner Tree and Group
Steiner Tree in Planar Graphs . . . . . 13:1--13:??
Jittat Fakcharoenphol and
Bundit Laekhanukit and
Danupon Nanongkai Faster Algorithms for Semi-Matching
Problems . . . . . . . . . . . . . . . . 14:1--14:??
T.-H. Hubert Chan and
Li Ning Fast Convergence for Consensus in
Dynamic Networks . . . . . . . . . . . . 15:1--15:??
Gonzalo Navarro and
Kunihiko Sadakane Fully Functional Static and Dynamic
Succinct Trees . . . . . . . . . . . . . 16:1--16:??
Dana Ron and
Gilad Tsur Testing Properties of Sparse Images . . 17:1--17:??
Konstantin Makarychev and
Rajsekar Manokaran and
Maxim Sviridenko Maximum Quadratic Assignment Problem:
Reduction from Maximum Label Cover and
LP-based Approximation Algorithm . . . . 18:1--18:??
Stefan Kratsch Co-Nondeterminism in Compositions: a
Kernelization Lower Bound for a
Ramsey-Type Problem . . . . . . . . . . 19:1--19:??
Stefan Kratsch and
Magnus Wahlström Compression via Matroids: a Randomized
Polynomial Kernel for Odd Cycle
Transversal . . . . . . . . . . . . . . 20:1--20:??
Holger Dell and
Thore Husfeldt and
Dániel Marx and
Nina Taslaman and
Martin Wahlén Exponential Time Complexity of the
Permanent and the Tutte Polynomial . . . 21:1--21:??
Dany Breslauer and
Zvi Galil Real-Time Streaming String-Matching . . 22:1--22:??
Djamal Belazzougui and
Gonzalo Navarro Alphabet-Independent Compressed Text
Indexing . . . . . . . . . . . . . . . . 23:1--23:??
Baruch Awerbuch and
Andrea Richa and
Christian Scheideler and
Stefan Schmid and
Jin Zhang Principles of Robust Medium Access and
an Application to Leader Election . . . 24:1--24:??
Yoann Dieudonné and
Andrzej Pelc and
David Peleg Gathering Despite Mischief . . . . . . . 1:1--1:??
Petra Berenbrink and
Martin Hoefer and
Thomas Sauerwald Distributed Selfish Load Balancing on
Networks . . . . . . . . . . . . . . . . 2:1--2:??
Nikhil Bansal and
Ravishankar Krishnaswamy and
Viswanath Nagarajan Better Scalable Algorithms for Broadcast
Scheduling . . . . . . . . . . . . . . . 3:1--3:??
Martin Grohe and
Dániel Marx Constraint Solving via Fractional Edge
Covers . . . . . . . . . . . . . . . . . 4:1--4:??
Piotr Berman and
Sofya Raskhodnikova Approximation Algorithms for Min-Max
Generalization Problems . . . . . . . . 5:1--5:??
Stephen Alstrup and
Mikkel Thorup and
Inge Li Gòrtz and
Theis Rauhe and
Uri Zwick Union-Find with Constant Time Deletions 6:1--6:??
Amit Chakrabarti and
Graham Cormode and
Andrew Mcgregor and
Justin Thaler Annotations in Data Streams . . . . . . 7:1--7:??
Joseph Cheriyan and
Bundit Laekhanukit and
Guyslain Naves and
Adrian Vetta Approximating Rooted Steiner Networks 8:1--8:??
Benjamin Doerr and
Tobias Friedrich and
Thomas Sauerwald Quasirandom Rumor Spreading . . . . . . 9:1--9:??
Yoann Dieudonné and
Andrzej Pelc Deterministic Network Exploration by
Anonymous Silent Agents with Local
Traffic Reports . . . . . . . . . . . . 10:1--10:??
Yufei Tao Dynamic Ray Stabbing . . . . . . . . . . 11:1--11:??
Richard Cole and
Carmit Hazay and
Moshe Lewenstein and
Dekel Tsur Two-Dimensional Parameterized Matching 12:1--12:??
Michael Dom and
Daniel Lokshtanov and
Saket Saurabh Kernelization Lower Bounds Through
Colors and IDs . . . . . . . . . . . . . 13:1--13:??
Erik D. Demaine and
Mohammadtaghi Hajiaghayi and
Dániel Marx Minimizing Movement: Fixed-Parameter
Tractability . . . . . . . . . . . . . . 14:1--14:??
Daniel Lokshtanov and
N. S. Narayanaswamy and
Venkatesh Raman and
M. S. Ramanujan and
Saket Saurabh Faster Parameterized Algorithms Using
Linear Programming . . . . . . . . . . . 15:1--15:??
Glencora Borradaile and
Piotr Sankowski and
Christian Wulff-Nilsen Min $ s t$-Cut Oracle for Planar Graphs
with Near-Linear Preprocessing Time . . 16:1--16:??
Stefanie Gerke and
Konstantinos Panagiotou and
Justus Schwartz and
Angelika Steger Maximizing the Minimum Load for Random
Processing Times . . . . . . . . . . . . 17:1--17:??
Bernadette Charron-Bost and
Matthias Függer and
Jennifer L. Welch and
Josef Widder Time Complexity of Link Reversal Routing 18:1--18:??
Glencora Borradaile and
Philip N. Klein and
Claire Mathieu A Polynomial-Time Approximation Scheme
for Euclidean Steiner Forest . . . . . . 19:1--19:??
Artur Jez Faster Fully Compressed Pattern Matching
by Recompression . . . . . . . . . . . . 20:1--20:??
Yixin Cao and
Dániel Marx Interval Deletion Is Fixed-Parameter
Tractable . . . . . . . . . . . . . . . 21:1--21:??
Sebastian Wild and
Markus E. Nebel and
Ralph Neininger Average Case and Distributional Analysis
of Dual-Pivot Quicksort . . . . . . . . 22:1--22:??
Inge Li Gòrtz and
Viswanath Nagarajan and
R. Ravi Minimum Makespan Multi-Vehicle
Dial-a-Ride . . . . . . . . . . . . . . 23:1--23:??
Reut Levi and
Dana Ron A Quasi-Polynomial Time Partition Oracle
for Graphs with an Excluded Minor . . . 24:1--24:??
Wiebke Höhn and
Tobias Jacobs On the Performance of Smith's Rule in
Single-Machine Scheduling with Nonlinear
Cost . . . . . . . . . . . . . . . . . . 25:1--25:??
Danny Z. Chen and
Haitao Wang Computing Shortest Paths among Curved
Obstacles in the Plane . . . . . . . . . 26:1--26:??
Dániel Marx and
László A. Végh Fixed-Parameter Algorithms for
Minimum-Cost Edge-Connectivity
Augmentation . . . . . . . . . . . . . . 27:1--27:??
Rajesh Chitnis and
Marek Cygan and
Mohammataghi Hajiaghayi and
Dániel Marx Directed Subset Feedback Vertex Set Is
Fixed-Parameter Tractable . . . . . . . 28:1--28:??
Rinat Ben Avraham and
Omrit Filtser and
Haim Kaplan and
Matthew J. Katz and
Micha Sharir The Discrete and Semicontinuous Fréchet
Distance with Shortcuts via Approximate
Distance Counting and Selection . . . . 29:1--29:??
Bernhard Haeupler and
Siddhartha Sen and
Robert E. Tarjan Rank-Balanced Trees . . . . . . . . . . 30:1--30:??
Djamal Belazzougui and
Gonzalo Navarro Optimal Lower and Upper Bounds for
Representing Sequences . . . . . . . . . 31:1--31:??
Patrizio Angelini and
Giuseppe Di Battista and
Fabrizio Frati and
Vít Jelínek and
Jan Kratochvíl and
Maurizio Patrignani and
Ignaz Rutter Testing Planarity of Partially Embedded
Graphs . . . . . . . . . . . . . . . . . 32:1--32:??
Jérémie Chalopin and
Shantanu Das and
Yann Disser and
Matús Mihalák and
Peter Widmayer Mapping Simple Polygons: The Power of
Telling Convex from Reflex . . . . . . . 33:1--33:??
Shayan Ehsani and
Saber Shokat Fadaee and
Mohammadamin Fazli and
Abbas Mehrabian and
Sina Sadeghian Sadeghabad and
Mohammadali Safari and
Morteza Saghafian A Bounded Budget Network Creation Game 34:1--34:??
Noa Avigdor-Elgrabli and
Yuval Rabani An Improved Competitive Algorithm for
Reordering Buffer Management . . . . . . 35:1--35:??
Yuval Rabani and
Andrea Richa and
Jared Saia and
David P. Woodruff Editorial to the Special Issue on
SODA'12 . . . . . . . . . . . . . . . . 1:1--1:??
Julia Chuzhoy and
Yury Makarychev and
Aravindan Vijayaraghavan and
Yuan Zhou Approximation Algorithms and Hardness of
the $k$-Route Cut Problem . . . . . . . 2:1--2:??
Guillaume Moroz and
Boris Aronov Computing the Distance between
Piecewise-Linear Bivariate Functions . . 3:1--3:??
Andreas Björklund and
Thore Husfeldt and
Petteri Kaski and
Mikko Koivisto and
Jesper Nederlof and
Pekka Parviainen Fast Zeta Transforms for Lattices with
Few Irreducibles . . . . . . . . . . . . 4:1--4:??
Alexandr Andoni and
Huy L. Nguyên Width of Points in the Streaming Model 5:1--5:??
Venkatesan Guruswami and
Prasad Raghavendra and
Rishi Saket and
Yi Wu Bypassing UGC from Some Optimal
Geometric Inapproximability Results . . 6:1--6:??
Ofer Neiman and
Shay Solomon Simple Deterministic Algorithms for
Fully Dynamic Maximal Matching . . . . . 7:1--7:??
Mihai P\uatra\cscu and
Mikkel Thorup On the $k$-Independence Required by
Linear Probing and Minwise Independence 8:1--8:??
Marcel K. De Carli Silva and
Nicholas J. A. Harvey and
Cristiane M. Sato Sparse Sums of Positive Semidefinite
Matrices . . . . . . . . . . . . . . . . 9:1--9:??
Anupam Gupta and
Viswanath Nagarajan and
R. Ravi Robust and MaxMin Optimization under
Matroid and Knapsack Uncertainty Sets 10:1--10:??
Loukas Georgiadis and
Robert E. Tarjan Dominator Tree Certification and
Divergent Spanning Trees . . . . . . . . 11:1--11:??
Oren Weimann and
Raphael Yuster Approximating the Diameter of Planar
Graphs in Near Linear Time . . . . . . . 12:1--12:??
Luká\vs Polá\vcek and
Ola Svensson Quasi-Polynomial Local Search for
Restricted Max-Min Fair Allocation . . . 13:1--13:??
Michael A. Bender and
Jeremy T. Fineman and
Seth Gilbert and
Robert E. Tarjan A New Approach to Incremental Cycle
Detection and Related Problems . . . . . 14:1--14:??
Ronald Graham and
Linus Hamilton and
Ariel Levavi and
Po-Shen Loh Anarchy Is Free in Network Creation . . 15:1--15:??
Thomas Bläsius and
Ignaz Rutter Simultaneous PQ-Ordering with
Applications to Constrained Embedding
Problems . . . . . . . . . . . . . . . . 16:1--16:??
Ioannis Koutis and
Alex Levin and
Richard Peng Faster Spectral Sparsification and
Numerical Algorithms for SDD Matrices 17:1--17:??
Martin Aumüller and
Martin Dietzfelbinger Optimal Partitioning for Dual-Pivot
Quicksort . . . . . . . . . . . . . . . 18:1--18:??
Miklós Ajtai and
Vitaly Feldman and
Avinatan Hassidim and
Jelani Nelson Sorting and Selection with Imprecise
Comparisons . . . . . . . . . . . . . . 19:1--19:??
Alon Efrat and
Sándor P. Fekete and
Joseph S. B. Mitchell and
Valentin Polishchuk and
Jukka Suomela Improved Approximation Algorithms for
Relay Placement . . . . . . . . . . . . 20:1--20:??
Eun Jung Kim and
Alexander Langer and
Christophe Paul and
Felix Reidl and
Peter Rossmanith and
Ignasi Sau and
Somnath Sikdar Linear Kernels and Single-Exponential
Algorithms Via Protrusion Decompositions 21:1--21:??
Ittai Abraham and
Shiri Chechik and
Cyril Gavoille and
David Peleg Forbidden-Set Distance Labels for Graphs
of Bounded Doubling Dimension . . . . . 22:1--22:??
Guy Kortsarz and
Zeev Nutov A Simplified $ 1.5$-Approximation
Algorithm for Augmenting
Edge-Connectivity of a Graph from $1$ to
$2$ . . . . . . . . . . . . . . . . . . 23:1--23:??
Harold N. Gabow The Minset-Poset Approach to
Representations of Graph Connectivity 24:1--24:??
Michael Dinitz and
Guy Kortsarz and
Ran Raz Label Cover Instances with Large Girth
and the Hardness of Approximating Basic
$k$-Spanner . . . . . . . . . . . . . . 25:1--25:??
Boris Aronov and
Anne Driemel and
Marc Van Kreveld and
Maarten Löffler and
Frank Staals Segmentation of Trajectories on
Nonmonotone Criteria . . . . . . . . . . 26:1--26:??
Goran Konjevod and
Andréa W. Richa and
Donglin Xia Scale-Free Compact Routing Schemes in
Networks of Low Doubling Dimension . . . 27:1--27:??
V. S. Anil Kumar and
Madhav V. Marathe and
Srinivasan Parthasarathy and
Aravind Srinivasan Distributed Algorithms for End-to-End
Packet Scheduling in Wireless Ad Hoc
Networks . . . . . . . . . . . . . . . . 28:1--28:??
Michael Elkin and
Shay Solomon Fast Constructions of Lightweight
Spanners for General Graphs . . . . . . 29:1--29:??
Glencora Borradaile and
Philip Klein The Two-Edge Connectivity
Survivable-Network Design Problem in
Planar Graphs . . . . . . . . . . . . . 30:1--30:??
Ioannis Koutis and
Ryan Williams Limits and Applications of Group
Algebras for Parameterized Problems . . 31:1--31:??
Christian Konrad and
Adi Rosén Approximating Semi-matchings in
Streaming and in Two-Party Communication 32:1--32:??
Thomas Bläsius and
Ignaz Rutter and
Dorothea Wagner Optimal Orthogonal Graph Drawing with
Convex Bend Costs . . . . . . . . . . . 33:1--33:??
Lisa Fleischer and
Rahul Garg and
Sanjiv Kapoor and
Rohit Khandekar and
Amin Saberi A Simple and Efficient Algorithm for
Computing Market Equilibria . . . . . . 34:1--34:??
Alexander Golovnev and
Alexander S. Kulikov and
Ivan Mihajlin Families with Infants: Speeding Up
Algorithms for NP-Hard Problems Using
FFT . . . . . . . . . . . . . . . . . . 35:1--35:??
Mohammadtaghi Hajiaghayi and
Wei Hu and
Jian Li and
Shi Li and
Barna Saha A Constant Factor Approximation
Algorithm for Fault-Tolerant $k$-Median 36:1--36:??
Anne Driemel and
Sariel Har-Peled and
Benjamin Raichel On the Expected Complexity of Voronoi
Diagrams on Terrains . . . . . . . . . . 37:1--37:??
Ron Adany and
Moran Feldman and
Elad Haramaty and
Rohit Khandekar and
Baruch Schieber and
Roy Schwartz and
Hadas Shachnai and
Tami Tamir All-Or-Nothing Generalized Assignment
with Application to Scheduling
Advertising Campaigns . . . . . . . . . 38:1--38:??
Philip Bille and
Johannes Fischer and
Inge Li Gòrtz and
Tsvi Kopelowitz and
Benjamin Sach and
Hjalte Wedel Vildhòj Sparse Text Indexing in Small Space . . 39:1--39:??
Stefan Kratsch and
Geevarghese Philip and
Saurabh Ray Point Line Cover: The Easy Kernel is
Essentially Tight . . . . . . . . . . . 40:1--40:??
Marek Cygan and
Holger Dell and
Daniel Lokshtanov and
Dániel Marx and
Jesper Nederlof and
Yoshio Okamoto and
Ramamohan Paturi and
Saket Saurabh and
Magnus Wahlström On Problems as Hard as CNF-SAT . . . . . 41:1--41:??
Amol Deshpande and
Lisa Hellerstein and
Devorah Kletenik Approximation Algorithms for Stochastic
Submodular Set Cover with Applications
to Boolean Function Evaluation and
Min-Knapsack . . . . . . . . . . . . . . 42:1--42:??
Adrian Dumitrescu and
Csaba D. Tóth The Traveling Salesman Problem for
Lines, Balls, and Planes . . . . . . . . 43:1--43:??
Siu-Wing Cheng and
Liam Mencel and
Antoine Vigneron A Faster Algorithm for Computing
Straight Skeletons . . . . . . . . . . . 44:1--44:??
Timothy M. Chan and
Bryan T. Wilkinson Adaptive and Approximate Orthogonal
Range Counting . . . . . . . . . . . . . 45:1--45:??
Karl Wimmer Agnostic Learning in
Permutation-Invariant Domains . . . . . 46:1--46:??
Justin Ward and
Stanislav Zivný Maximizing $k$-Submodular Functions and
Beyond . . . . . . . . . . . . . . . . . 47:1--47:??
Arkadiusz Socala Tight Lower Bound for the Channel
Assignment Problem . . . . . . . . . . . 48:1--48:??
Chaitanya Swamy Improved Approximation Algorithms for
Matroid and Knapsack Median Problems and
Applications . . . . . . . . . . . . . . 49:1--49:??
Michael Elkin and
Seth Pettie A Linear-Size Logarithmic Stretch
Path-Reporting Distance Oracle for
General Graphs . . . . . . . . . . . . . 50:1--50:??
Yuval Emek and
Magnús M. Halldórsson and
Adi Rosén Space-Constrained Interval Selection . . 51:1--51:??
Paolo Ferragina and
Rossano Venturini Compressed Cache-Oblivious String B-Tree 52:1--52:??
Meng He and
J. Ian Munro and
Gelin Zhou Data Structures for Path Queries . . . . 53:1--53:??
Mohammad Taghi Hajiaghayi and
Rohit Khandekar and
Mohammad Reza Khani and
Guy Kortsarz Approximation Algorithms for Movement
Repairmen . . . . . . . . . . . . . . . 54:1--54:??
T.-H. Hubert Chan and
Anupam Gupta and
Bruce M. Maggs and
Shuheng Zhou On Hierarchical Routing in Doubling
Metrics . . . . . . . . . . . . . . . . 55:1--55:??
Loukas Georgiadis and
Robert E. Tarjan Addendum to ``Dominator Tree
Certification and Divergent Spanning
Trees'' . . . . . . . . . . . . . . . . 56:1--56:??
Siddhartha Sen and
Robert E. Tarjan and
David Hong Kyun Kim Deletion Without Rebalancing in Binary
Search Trees . . . . . . . . . . . . . . 57:1--57:??
Ravishankar Krishnaswamy and
Maxim Sviridenko Inapproximability of the Multilevel
Uncapacitated Facility Location Problem 1:1--1:??
Per Austrin and
Siavosh Benabbas and
Konstantinos Georgiou Better Balance by Being Biased: a
0.8776-Approximation for Max Bisection 2:1--2:??
Pankaj K. Agarwal and
Boris Aronov and
Sariel Har-Peled and
Jeff M. Phillips and
Ke Yi and
Wuzhou Zhang Nearest-Neighbor Searching Under
Uncertainty II . . . . . . . . . . . . . 3:1--3:??
Andrew Shallue Tabulating Pseudoprimes and Tabulating
Liars . . . . . . . . . . . . . . . . . 4:1--4:??
Ken-Ichi Kawarabayashi and
Yusuke Kobayashi An Improved Approximation Algorithm for
the Edge-Disjoint Paths Problem with
Congestion Two . . . . . . . . . . . . . 5:1--5:??
Yuval Emek and
Adi Rosén Semi-Streaming Set Cover . . . . . . . . 6:1--6:??
Edith Cohen and
Graham Cormode and
Nick Duffield and
Carsten Lund On the Tradeoff between Stability and
Fit . . . . . . . . . . . . . . . . . . 7:1--7:??
Martin Aumüller and
Martin Dietzfelbinger and
Pascal Klaue How Good Is Multi-Pivot Quicksort? . . . 8:1--8:??
Loukas Georgiadis and
Giuseppe F. Italiano and
Luigi Laura and
Nikos Parotsidis $2$-Edge Connectivity in Directed Graphs 9:1--9:??
Matthias Englert and
Heiko Röglin and
Berthold Vöcking Smoothed Analysis of the $2$-Opt
Algorithm for the General TSP . . . . . 10:1--10:??
Merav Parter and
David Peleg Sparse Fault-Tolerant BFS Structures . . 11:1--11:??
Erel Segal-Halevi and
Avinatan Hassidim and
Yonatan Aumann Waste Makes Haste: Bounded Time
Algorithms for Envy-Free Cake Cutting
with Free Disposal . . . . . . . . . . . 12:1--12:??
Sungjin Im and
Viswanath Nagarajan and
Ruben Van Der Zwaan Minimum Latency Submodular Cover . . . . 13:1--13:??
Robert Krauthgamer and
Tal Wagner Cheeger-Type Approximation for Sparsest
$ s t$-Cut . . . . . . . . . . . . . . . 14:1--14:??
Elisabeth Lübbecke and
Olaf Maurer and
Nicole Megow and
Andreas Wiese A New Approach to Online Scheduling:
Approximating the Optimal Competitive
Ratio . . . . . . . . . . . . . . . . . 15:1--15:??
Maxim Babenko and
Andrew V. Goldberg and
Anupam Gupta and
Viswanath Nagarajan Algorithms for Hub Label Optimization 16:1--16:??
David G. Harris Lopsidependency in the Moser--Tardos
Framework: Beyond the Lopsided Lovász
Local Lemma . . . . . . . . . . . . . . 17:1--17:??
Alexandr Andoni and
Debmalya Panigrahi and
Marcin Pilipczuk Editorial . . . . . . . . . . . . . . . 18:1--18:??
Keren Censor-Hillel and
Mohsen Ghaffari and
George Giakkoupis and
Bernhard Haeupler and
Fabian Kuhn Tight Bounds on Vertex Connectivity
Under Sampling . . . . . . . . . . . . . 19:1--19:??
Deeparnab Chakrabarty and
Kashyap Dixit and
Madhav Jha and
C. Seshadhri Property Testing on Product
Distributions: Optimal Testers for
Bounded Derivative Properties . . . . . 20:1--20:??
Hyung-Chan An and
Ashkan Norouzi-Fard and
Ola Svensson Dynamic Facility Location via
Exponential Clocks . . . . . . . . . . . 21:1--21:??
Shi Li On Uniform Capacitated $k$-Median Beyond
the Natural LP Relaxation . . . . . . . 22:1--22:??
Jaroslaw Byrka and
Thomas Pensyl and
Bartosz Rybicki and
Aravind Srinivasan and
Khoa Trinh An Improved Approximation for $k$-Median
and Positive Correlation in Budgeted
Optimization . . . . . . . . . . . . . . 23:1--23:??
Axel Bacher and
Olivier Bodini and
Hsien-Kuei Hwang and
Tsung-Hsi Tsai Generating Random Permutations by Coin
Tossing: Classical Algorithms, New
Analysis, and Modern Implementation . . 24:1--24:43
Michael Etscheid and
Heiko Röglin Smoothed Analysis of Local Search for
the Maximum-Cut Problem . . . . . . . . 25:1--25:??
Haim Kaplan and
Shay Mozes and
Yahav Nussbaum and
Micha Sharir Submatrix Maximum Queries in Monge
Matrices and Partial Monge Matrices, and
Their Applications . . . . . . . . . . . 26:1--26:??
Siu-Wing Cheng and
Jiongxin Jin and
Man-Kit Lau A Fast and Simple Surface Reconstruction
Algorithm . . . . . . . . . . . . . . . 27:1--27:??
Roberto Grossi and
John Iacono and
Gonzalo Navarro and
Rajeev Raman and
S. Rao Satti Asymptotically Optimal Encodings of
Range Data Structures for Selection and
Top-$k$ Queries . . . . . . . . . . . . 28:1--28:??
Robert Ganian and
M. S. Ramanujan and
Stefan Szeider Discovering Archipelagos of Tractability
for Constraint Satisfaction and Counting 29:1--29:??
Keren Cohavi and
Shahar Dobzinski Faster and Simpler Sketches of Valuation
Functions . . . . . . . . . . . . . . . 30:1--30:??
Christian Glacet and
Avery Miller and
Andrzej Pelc Time vs. Information Tradeoffs for
Leader Election in Anonymous Trees . . . 31:1--31:??
Anna C. Gilbert and
Yi Li and
Ely Porat and
Martin J. Strauss For-All Sparse Recovery in Near-Optimal
Time . . . . . . . . . . . . . . . . . . 32:1--32:??
David G. Harris and
Aravind Srinivasan Algorithmic and Enumerative Aspects of
the Moser--Tardos Distribution . . . . . 33:1--33:??
Mahdi Cheraghchi and
Piotr Indyk Nearly Optimal Deterministic Algorithm
for Sparse Walsh--Hadamard Transform . . 34:1--34:??
Archontia C. Giannopoulou and
Bart M. P. Jansen and
Daniel Lokshtanov and
Saket Saurabh Uniform Kernelization Complexity of
Hitting Forbidden Minors . . . . . . . . 35:1--35:??
Fedor V. Fomin and
Daniel Lokshtanov and
Fahad Panolan and
Saket Saurabh Representative Families of Product
Families . . . . . . . . . . . . . . . . 36:1--36:??
Chidambaram Annamalai and
Christos Kalaitzis and
Ola Svensson Combinatorial Algorithm for Restricted
Max--Min Fair Allocation . . . . . . . . 37:1--37:??
Michael A. Bender and
Martín Farach-Colton and
Sándor P. Fekete and
Jeremy T. Fineman and
Seth Gilbert Cost-Oblivious Storage Reallocation . . 38:1--38:??
Moran Feldman Maximizing Symmetric Submodular
Functions . . . . . . . . . . . . . . . 39:1--39:??
Michael Dinitz and
Guy Kortsarz and
Zeev Nutov Improved Approximation Algorithm for
Steiner $k$-Forest with Nearly Uniform
Weights . . . . . . . . . . . . . . . . 40:1--40:??
Allan Borodin and
Aadhar Jain and
Hyun Chul Lee and
Yuli Ye Max-Sum Diversification, Monotone
Submodular Functions, and Dynamic
Updates . . . . . . . . . . . . . . . . 41:1--41:??
Thomas Dueholm Hansen and
Haim Kaplan and
Robert E. Tarjan and
Uri Zwick Hollow Heaps . . . . . . . . . . . . . . 42:1--42:??
Marek Cygan and
Fabrizio Grandoni and
Danny Hermelin Tight Kernel Bounds for Problems on
Graphs with Small Degeneracy . . . . . . 43:1--43:??
Serge Gaspers and
Gregory B. Sorkin Separate, Measure and Conquer: Faster
Polynomial-Space Algorithms for Max
$2$-CSP and Counting Dominating Sets . . 44:1--44:??
Harold N. Gabow A Data Structure for Nearest Common
Ancestors with Linking . . . . . . . . . 45:1--45:??
M. S. Ramanujan and
Saket Saurabh Linear-Time Parameterized Algorithms via
Skew-Symmetric Multicuts . . . . . . . . 46:1--46:??
Hsien-Kuei Hwang and
Svante Janson and
Tsung-Hsi Tsai Exact and Asymptotic Solutions of a
Divide-and-Conquer Recurrence Dividing
at Half: Theory and Applications . . . . 47:1--47:??
Andreas Björklund and
Petteri Kaski and
Lukasz Kowalik Counting Thin Subgraphs via Packings
Faster than Meet-in-the-Middle Time . . 48:1--48:??
Takuro Fukunaga Spider Covers for Prize-Collecting
Network Activation Problem . . . . . . . 49:1--49:??
Elaine Shi and
T.-H. Hubert Chan and
Eleanor Rieffel and
Dawn Song Distributed Private Data Analysis: Lower
Bounds and Practical Constructions . . . 50:1--50:??
Monika Henzinger and
Sebastian Krinninger and
Danupon Nanongkai Sublinear-Time Maintenance of
Breadth-First Spanning Trees in
Partially Dynamic Networks . . . . . . . 51:1--51:??
Georgios Amanatidis and
Evangelos Markakis and
Afshin Nikzad and
Amin Saberi Approximation Algorithms for Computing
Maximin Share Allocations . . . . . . . 52:1--52:??
Bernhard Haeupler and
David G. Harris Parallel Algorithms and Concentration
Bounds for the Lovász Local Lemma via
Witness DAGs . . . . . . . . . . . . . . 53:1--53:??
Konstantin Makarychev and
Maxim Sviridenko Maximizing Polynomials Subject to
Assignment Constraints . . . . . . . . . 54:1--54:??
Amr Elmasry Toward Optimal Self-Adjusting Heaps . . 55:1--55:??
Rezaul A. Chowdhury and
Vijaya Ramachandran Cache-Oblivious Buffer Heap and
Cache-Efficient Computation of Shortest
Paths in Graphs . . . . . . . . . . . . 1:1--1:??
David Eppstein The Parametric Closure Problem . . . . . 2:1--2:??
Daniel Lokshtanov and
Marcin Pilipczuk and
Erik Jan Van Leeuwen Independence and Efficient Domination on
$ P_6 $-free Graphs . . . . . . . . . . 3:1--3:??
Stephan Held and
Sophie Theresa Spirkl Binary Adder Circuits of Asymptotically
Minimum Depth, Linear Size, and Fan-Out
Two . . . . . . . . . . . . . . . . . . 4:1--4:??
Nikhil R. Devanur and
Zhiyi Huang Primal Dual Gives Almost Optimal
Energy-Efficient Online Algorithms . . . 5:1--5:??
Fedor V. Fomin and
Daniel Lokshtanov and
Saket Saurabh and
Dimitrios M. Thilikos Kernels for (Connected) Dominating Set
on Graphs with Excluded Topological
Minors . . . . . . . . . . . . . . . . . 6:1--6:??
Daniel Lokshtanov and
M. S. Ramanujan and
Saket Saurabh Linear Time Parameterized Algorithms for
Subset Feedback Vertex Set . . . . . . . 7:1--7:??
Ran Duan and
Seth Pettie and
Hsin-Hao Su Scaling Algorithms for Weighted Matching
in General Graphs . . . . . . . . . . . 8:1--8:??
T.-H. Hubert Chan and
Shaofeng H.-C. Jiang Reducing Curse of Dimensionality:
Improved PTAS for TSP (with
Neighborhoods) in Doubling Metrics . . . 9:1--9:??
Merav Parter and
David Peleg Fault-Tolerant Approximate BFS
Structures . . . . . . . . . . . . . . . 10:1--10:??
Timothy M. Chan and
J. Ian Munro and
Venkatesh Raman Selection and Sorting in the ``Restore''
Model . . . . . . . . . . . . . . . . . 11:1--11:??
T.-H. Hubert Chan and
Fei Chen and
Xiaowei Wu Analyzing Node-Weighted Oblivious
Matching Problem via Continuous LP with
Jump Discontinuity . . . . . . . . . . . 12:1--12:??
Daniel Lokshtanov and
Dániel Marx and
Saket Saurabh Known Algorithms on Graphs of Bounded
Treewidth Are Probably Optimal . . . . . 13:1--13:??
Daniel Lokshtanov and
Pranabendu Misra and
Fahad Panolan and
Saket Saurabh Deterministic Truncation of Linear
Matroids . . . . . . . . . . . . . . . . 14:1--14:??
Torsten MÜTZE and
Jerri Nummenpalo Efficient Computation of Middle Levels
Gray Codes . . . . . . . . . . . . . . . 15:1--15:??
Sara Ahmadian and
Babak Behsaz and
Zachary Friggstad and
Amin Jorati and
Mohammad R. Salavatipour and
Chaitanya Swamy Approximation Algorithms for
Minimum-Load $k$-Facility Location . . . 16:1--16:??
Gramoz Goranci and
Monika Henzinger and
Mikkel Thorup Incremental Exact Min-Cut in
Polylogarithmic Amortized Update Time 17:1--17:??
Evangelos Anagnostopoulos and
Ioannis Z. Emiris and
Ioannis Psarros Randomized Embeddings with Slack and
High-Dimensional Approximate Nearest
Neighbor . . . . . . . . . . . . . . . . 18:1--18:??
Alantha Newman and
Heiko Röglin and
Johanna Seif The Alternating Stock Size Problem and
the Gasoline Puzzle . . . . . . . . . . 19:1--19:??
Ademir Hujdurovi\'c and
Edin Husi\'c and
Martin Milani\'c and
Romeo Rizzi and
Alexandru I. Tomescu Perfect Phylogenies via Branchings in
Acyclic Digraphs and a Generalization of
Dilworth's Theorem . . . . . . . . . . . 20:1--20:??
Marcin Bienkowski and
Tomasz Jurdzinski and
Miros\law Korzeniowski and
Dariusz R. Kowalski Distributed Online and Stochastic
Queueing on a Multiple Access Channel 21:1--21:??
Andreas Schmid and
Jens M. Schmidt Computing $2$-Walks in Polynomial Time 22:1--22:??
Zhewei Wei and
Ke Yi Tight Space Bounds for Two-Dimensional
Approximate Range Counting . . . . . . . 23:1--23:??
Pankaj K. Agarwal and
Kyle Fox and
Abhinandan Nath and
Anastasios Sidiropoulos and
Yusu Wang Computing the Gromov--Hausdorff Distance
for Metric Trees . . . . . . . . . . . . 24:1--24:??
Pradeesha Ashok and
Fedor V. Fomin and
Sudeshna Kolay and
Saket Saurabh and
Meirav Zehavi Exact Algorithms for Terrain Guarding 25:1--25:??
Arnab Bhattacharyya and
Fabrizio Grandoni and
Aleksandar Nikolov and
Barna Saha and
Saket Saurabh and
Aravindan Vijayaraghavan and
Qin Zhang Editorial: ACM-SIAM Symposium on
Discrete Algorithms (SODA) 2016 Special
Issue . . . . . . . . . . . . . . . . . 26:1--26:??
Amir Abboud and
Arturs Backurs and
Thomas Dueholm Hansen and
Virginia Vassilevska Williams and
Or Zamir Subtree Isomorphism Revisited . . . . . 27:1--27:??
Samuel B. Hopkins and
Pravesh Kothari and
Aaron Henry Potechin and
Prasad Raghavendra and
Tselil Schramm On the Integrality Gap of Degree-4 Sum
of Squares for Planted Clique . . . . . 28:1--28:??
Rasmus Pagh CoveringLSH: Locality-Sensitive Hashing
without False Negatives . . . . . . . . 29:1--29:??
Timothy M. CHAN Improved Deterministic Algorithms for
Linear Programming in Low Dimensions . . 30:1--30:??
Matti Karppa and
Petteri Kaski and
Jukka Kohonen A Faster Subquadratic Algorithm for
Finding Outlier Correlations . . . . . . 31:1--31:??
Niv Buchbinder and
Moran Feldman Deterministic Algorithms for Submodular
Maximization Problems . . . . . . . . . 32:1--32:??
Shiri Chechik and
Christian Wulff-Nilsen Near-Optimal Light Spanners . . . . . . 33:1--33:??
Fedor V. Fomin and
Daniel Lokshtanov and
Saket Saurabh and
MichaL Pilipczuk and
Marcin Wrochna Fully Polynomial-Time Parameterized
Computations for Graphs and Matrices of
Low Treewidth . . . . . . . . . . . . . 34:1--34:??
Ivan Bliznets and
Fedor V. Fomin and
Marcin Pilipczuk and
MichaL Pilipczuk Subexponential Parameterized Algorithm
for Interval Completion . . . . . . . . 35:1--35:??
Mark De Berg and
Joachim Gudmundsson and
Mehran Mehr Faster Algorithms for Computing
Plurality Points . . . . . . . . . . . . 36:1--36:??
Suguru Tamaki and
Yuichi Yoshida Approximation Guarantees for the Minimum
Linear Arrangement Problem by Higher
Eigenvalues . . . . . . . . . . . . . . 1--13
Robert Krauthgamer and
Ohad Trabelsi Conditional Lower Bounds for All-Pairs
Max-Flow . . . . . . . . . . . . . . . . 1--15
Jérémy Barbay and
Pablo Pérez-Lantero Adaptive Computation of the Swap-Insert
Correction Distance . . . . . . . . . . 1--16
Omer Gold and
Micha Sharir Dynamic Time Warping and Geometric Edit
Distance: Breaking the Quadratic Barrier 1--17
Pankaj K. Agarwal and
Kyle Fox and
Oren Salzman An Efficient Algorithm for Computing
High-Quality Paths amid Polygonal
Obstacles . . . . . . . . . . . . . . . 1--21
Jean-Daniel Boissonnat and
Karthik C. S. An Efficient Representation for
Filtrations of Simplicial Complexes . . 1--21
Aris Anagnostopoulos and
Fabrizio Grandoni and
Stefano Leonardi and
Andreas Wiese A Mazing $ 2 + \epsilon $ Approximation
for Unsplittable Flow on a Path . . . . 1--23
Hossein Esfandiari and
Mohammadtaghi Hajiaghayi and
Vahid Liaghat and
Morteza Monemizadeh and
Krzysztof Onak Streaming Algorithms for Estimating the
Matching Size in Planar Graphs and
Beyond . . . . . . . . . . . . . . . . . 1--23
Amos Korman and
Yoav Rodeh The Dependent Doors Problem: an
Investigation into Sequential Decisions
without Feedback . . . . . . . . . . . . 1--23
Patrizio Angelini and
Giordano Da Lozzo and
Giuseppe Di Battista and
Valentino Di Donato and
Philipp Kindermann and
Günter Rote and
Ignaz Rutter Windrose Planarity: Embedding Graphs
with Direction-Constrained Edges . . . . 1--24
Lin Chen and
Guochuan Zhang Packing Groups of Items into Multiple
Knapsacks . . . . . . . . . . . . . . . 1--24
David G. Harris Deterministic Parallel Algorithms for
Fooling Polylogarithmic Juntas and the
Lovász Local Lemma . . . . . . . . . . . 1--24
Boris Aronov and
Matthew J. Katz Batched Point Location in SINR Diagrams
via Algebraic Tools . . . . . . . . . . 1--29
T.-H. Hubert Chan and
Zhiyi Huang and
Shaofeng H.-C. Jiang and
Ning Kang and
Zhihao Gavin Tang Online Submodular Maximization with Free
Disposal . . . . . . . . . . . . . . . . 1--29
Sampath Kannan and
Claire Mathieu and
Hang Zhou Graph Reconstruction and Verification 1--30
Edith Cohen Stream Sampling Framework and
Application for Frequency Cap Statistics 1--40
Marcin Pilipczuk and
Micha\l Pilipczuk and
Piotr Sankowski and
Erik Jan Van Leeuwen Network Sparsification for Steiner
Problems on Planar and Bounded-Genus
Graphs . . . . . . . . . . . . . . . . . 1--73
Barun Gorain and
Andrzej Pelc Deterministic Graph Exploration with
Advice . . . . . . . . . . . . . . . . . 1--17
Anna Adamaszek and
Artur Czumaj and
Matthias Englert and
Harald Räcke An $ O(\log k) $-Competitive Algorithm
for Generalized Caching . . . . . . . . 1--18
Yann Disser and
Martin Skutella The Simplex Algorithm Is NP-Mighty . . . 1--19
Daniel Lokshtanov and
Amer E. Mouawad The Complexity of Independent Set
Reconfiguration on Bipartite Graphs . . 1--19
Mikkel Abrahamsen and
Bartosz Walczak Common Tangents of Two Disjoint Polygons
in Linear Time and Constant Workspace 1--21
Petra Berenbrink and
Ralf Klasing and
Adrian Kosowski and
Frederik Mallmann-Trenn and
Przemys\law Uzna\'nski Improved Analysis of Deterministic
Load-Balancing Schemes . . . . . . . . . 1--22
Zbigniew Go\l\kebiewski and
Abram Magner and
Wojciech Szpankowski Entropy and Optimal Compression of Some
General Plane Trees . . . . . . . . . . 1--23
Zhengyang Liu and
Xi Chen and
Rocco A. Servedio and
Ying Sheng and
Jinyu Xie Distribution-free Junta Testing . . . . 1--23
Hiroshi Hirai A Dual Descent Algorithm for
Node-capacitated Multiflow Problems and
Its Applications . . . . . . . . . . . . 1--24
Marek Cygan and
Marcin Mucha and
Karol W\kegrzycki and
Micha\l W\lodarczyk On Problems Equivalent to $ (\min,
+)$-Convolution . . . . . . . . . . . . 1--25
Arnab Bhattacharyya and
Palash Dey and
David P. Woodruff An Optimal Algorithm for $ l_1$-Heavy
Hitters in Insertion Streams and Related
Problems . . . . . . . . . . . . . . . . 1--27
Fedor V. Fomin and
Petr A. Golovach and
Daniel Lokshtanov and
Saket Saurabh and
Meirav Zehavi Clique-width III: Hamiltonian Cycle and
the Odd Case of Graph Coloring . . . . . 1--27
Akanksha Agrawal and
Daniel Lokshtanov and
Pranabendu Misra and
Saket Saurabh and
Meirav Zehavi Feedback Vertex Set Inspired Kernel for
Chordal Vertex Deletion . . . . . . . . 1--28
Michael Elkin and
Ofer Neiman Efficient Algorithms for Constructing
Very Sparse Spanners and Emulators . . . 1--29
Fedor V. Fomin and
Tien-Nam Le and
Daniel Lokshtanov and
Saket Saurabh and
Stéphan Thomassé and
Meirav Zehavi Subquadratic Kernels for Implicit
$3$-Hitting Set and $3$-Set Packing
Problems . . . . . . . . . . . . . . . . 1--44
Aravind Srinivasan Editorial . . . . . . . . . . . . . . . 1--1
Dániel Marx and
Virgi Vassilevska Williams and
Neal E. Young Introduction to the Special Issue on
SODA 2017 . . . . . . . . . . . . . . . 1--2
Ami Paz and
Gregory Schwartzman A $ (2 + \epsilon)$-Approximation for
Maximum Weight Matching in the
Semi-streaming Model . . . . . . . . . . 1--15
Stephan Kreutzer and
Roman Rabinovich and
Sebastian Siebertz Polynomial Kernels and Wideness
Properties of Nowhere Dense Graph
Classes . . . . . . . . . . . . . . . . 1--19
Veli Mäkinen and
Alexandru I. Tomescu and
Anna Kuosmanen and
Topi Paavilainen and
Travis Gagie and
Rayan Chikhi Sparse Dynamic Programming on DAGs with
Small Width . . . . . . . . . . . . . . 1--21
David Adjiashvili Beating Approximation Factor Two for
Weighted Tree Augmentation with Bounded
Costs . . . . . . . . . . . . . . . . . 1--26
Nikhil Bansal and
Marek Elié\vs and
\Lukasz Je\.z and
Grigorios Koumoutsos The $ (h, k)$-Server Problem on Bounded
Depth Trees . . . . . . . . . . . . . . 1--26
Zachary Friggstad and
Kamyar Khodamoradi and
Mohsen Rezapour and
Mohammad R. Salavatipour Approximation Schemes for Clustering
with Outliers . . . . . . . . . . . . . 1--26
David Adjiashvili and
Andrea Baggio and
Rico Zenklusen Firefighting on Trees Beyond Integrality
Gaps . . . . . . . . . . . . . . . . . . 1--33
Alexandr Kazda and
Vladimir Kolmogorov and
Michal Rol\'ìnek Even Delta-Matroids and the Complexity
of Planar Boolean CSPs . . . . . . . . . 1--33
Jiawei Gao and
Russell Impagliazzo and
Antonina Kolokolova and
Ryan Williams Completeness for First-order Properties
on Sparse Structures with Algorithmic
Applications . . . . . . . . . . . . . . 1--35
Sergio Cabello Subquadratic Algorithms for the Diameter
and the Sum of Pairwise Distances in
Planar Graphs . . . . . . . . . . . . . 1--38
Diodato Ferraioli and
Carmine Ventre Metastability of the Logit Dynamics for
Asymptotically Well-Behaved Potential
Games . . . . . . . . . . . . . . . . . 1--42
Danny Hermelin and
Matthias Mnich and
Erik Jan Van Leeuwen and
Gerhard Woeginger Domination When the Stars Are Out . . . 1--90
Sampath Kannan and
Kevin T. Tian Locating Errors in Faulty Formulas . . . 1--13
Deeparnab Chakrabarty and
Maryam Negahbani Generalized Center Problems with
Outliers . . . . . . . . . . . . . . . . 1--14
Zhiyi Huang and
Zhihao Gavin Tang and
Xiaowei Wu and
Yuhao Zhang Online Vertex-Weighted Bipartite
Matching: Beating $ 1 - 1 / e $ with
Random Arrivals . . . . . . . . . . . . 1--15
Avrim Blum and
Sariel Har-Peled and
Benjamin Raichel Sparse Approximation via Generating
Point Sets . . . . . . . . . . . . . . . 1--16
Saeed Akhoondian Amiri and
Stefan Schmid and
Sebastian Siebertz Distributed Dominating Set
Approximations beyond Planar Graphs . . 1--18
Konstantinos Koiliaris and
Chao Xu Faster Pseudopolynomial Time Algorithms
for Subset Sum . . . . . . . . . . . . . 1--20
Yeow Meng Chee and
Johan Chrisnata and
Han Mao Kiah and
Tuan Thanh Nguyen Deciding the Confusability of Words
under Tandem Repeats in Linear Time . . 1--22
David G. Harris and
Thomas Pensyl and
Aravind Srinivasan and
Khoa Trinh A Lottery Model for Center-Type Problems
With Outliers . . . . . . . . . . . . . 1--25
Klaus Jansen and
Marten Maack and
Malin Rau Approximation Schemes for Machine
Scheduling with Resource (In-)dependent
Processing Times . . . . . . . . . . . . 1--28
David G. Harris Derandomized Concentration Bounds for
Polynomials, and Hypergraph Maximal
Independent Set . . . . . . . . . . . . 1--29
Moni Naor and
Yogev Eylon Bloom Filters in Adversarial
Environments . . . . . . . . . . . . . . 1--30
Niv Buchbinder and
Moran Feldman and
Roy Schwartz Online Submodular Maximization with
Preemption . . . . . . . . . . . . . . . 1--31
Xiaohui Bei and
Jugal Garg and
Martin Hoefer Ascending-Price Algorithms for Unknown
Markets . . . . . . . . . . . . . . . . 1--33
Hiroshi Hirai and
Yuni Iwamasa and
Kazuo Murota and
Stanislav \vZivný A Tractable Class of Binary VCSPs via
$M$-Convex Intersection . . . . . . . . 1--41
David Coudert and
Guillaume Ducoffe and
Alexandru Popa Fully Polynomial FPT Algorithms for Some
Classes of Bounded Clique-width Graphs 1--57
Massimo Cairo and
Paul Medvedev and
Nidia Obscura Acosta and
Romeo Rizzi and
Alexandru I. Tomescu An Optimal $ O(n m) $ Algorithm for
Enumerating All Walks Common to All
Closed Edge-covering Walks of a Graph 1--17
Marek Cygan and
\Lukasz Kowalik and
Arkadiusz Soca\la Improving TSP Tours Using Dynamic
Programming over Tree Decompositions . . 1--19
Marcin Bienkowski and
Jaros\law Byrka and
Marcin Mucha Dynamic Beats Fixed: On Phase-based
Algorithms for File Migration . . . . . 1--21
Ulrich Brenner and
Anna Hermann Faster Carry Bit Computation for Adder
Circuits with Prescribed Arrival Times 1--23
Boris Klemz and
Günter Rote Ordered Level Planarity and Its
Relationship to Geodesic Planarity,
Bi-Monotonicity, and Variations of Level
Planarity . . . . . . . . . . . . . . . 1--25
Hugo A. Akitaya and
Radoslav Fulek and
Csaba D. Tóth Recognizing Weak Embeddings of Graphs 1--27
Sandy Heydrich and
Andreas Wiese Faster Approximation Schemes for the
Two-Dimensional Knapsack Problem . . . . 1--28
Christoph Hunkenschröder and
Santosh Vempala and
Adrian Vetta A $ 4 / 3$-Approximation Algorithm for
the Minimum $2$-Edge Connected Subgraph
Problem . . . . . . . . . . . . . . . . 1--28
Yi-Jun Chang and
Tsvi Kopelowitz and
Seth Pettie and
Ruosong Wang and
Wei Zhan Exponential Separations in the Energy
Complexity of Leader Election . . . . . 1--31
Fedor V. Fomin and
Petr A. Golovach and
Daniel Lokshtanov and
Saket Saurabh Spanning Circuits in Regular Matroids 1--38
Mark Bun and
Jelani Nelson and
Uri Stemmer Heavy Hitters and the Structure of Local
Privacy . . . . . . . . . . . . . . . . 1--40
Yin Tat Lee and
Marcin Pilipczuk and
David Woodruff Introduction to the Special Issue on
SODA'18 . . . . . . . . . . . . . . . . 1:1--1:2
Mudabir Kabir Asathulla and
Sanjeev Khanna and
Nathaniel Lahn and
Sharath Raghvendra A Faster Algorithm for Minimum-cost
Bipartite Perfect Matching in Planar
Graphs . . . . . . . . . . . . . . . . . 2:1--2:30
Jaros\law B\lasiok Optimal Streaming and Tracking Distinct
Elements with High Probability . . . . . 3:1--3:28
Chloe Ching-Yun Hsu and
Chris Umans A New Algorithm for Fast Generalized
DFTs . . . . . . . . . . . . . . . . . . 4:1--4:20
Friedrich Eisenbrand and
Robert Weismantel Proximity Results and Faster Algorithms
for Integer Programming Using the
Steinitz Lemma . . . . . . . . . . . . . 5:1--5:14
Manuela Fischer and
Andreas Noever Tight Analysis of Parallel Randomized
Greedy MIS . . . . . . . . . . . . . . . 6:1--6:13
Timothy M. Chan More Logarithmic-factor Speedups for
3SUM, (median,+)-convolution, and Some
Geometric 3SUM-hard Problems . . . . . . 7:1--7:23
Yi-Jun Chang and
Qizheng He and
Wenzheng Li and
Seth Pettie and
Jara Uitto Distributed Edge Coloring and a Special
Case of the Constructive Lovász Local
Lemma . . . . . . . . . . . . . . . . . 8:1--8:51
Clifford Stein and
Mingxian Zhong Scheduling When You Do Not Know the
Number of Machines . . . . . . . . . . . 9:1--9:20
Brian Brubach and
Karthik A. Sankararaman and
Aravind Srinivasan and
Pan Xu Algorithms to Approximate Column-sparse
Packing Problems . . . . . . . . . . . . 10:1--10:32
Joe Sawada and
Aaron Williams Solving the Sigma--Tau Problem . . . . . 11:1--11:17
Fedor V. Fomin and
Petr A. Golovach and
Daniel Lokshtanov and
Fahad Panolan and
Saket Saurabh Approximation Schemes for Low-rank
Binary Matrix Approximation Problems . . 12:1--12:39
Gopal Pandurangan and
Peter Robinson and
Michele Scquizzato A Time- and Message-Optimal Distributed
Algorithm for Minimum Spanning Trees . . 13:1--13:27
Ashish Chiplunkar and
Sundar Vishwanathan Randomized Memoryless Algorithms for the
Weighted and the Generalized $k$-server
Problems . . . . . . . . . . . . . . . . 14:1--14:28
Fabrizio Grandoni and
Virginia Vassilevska Williams Faster Replacement Paths and Distance
Sensitivity Oracles . . . . . . . . . . 15:1--15:25
Pawe\l Gawrychowski and
Shay Mozes and
Oren Weimann Submatrix Maximum Queries in Monge and
Partial Monge Matrices Are Equivalent to
Predecessor Search . . . . . . . . . . . 16:1--16:24
Djamal Belazzougui and
Fabio Cunial and
Juha Kärkkäinen and
Veli Mäkinen Linear-time String Indexing and Analysis
in Small Space . . . . . . . . . . . . . 17:1--17:54
Talya Eden and
Reut Levi and
Dana Ron Testing Bounded Arboricity . . . . . . . 18:1--18:22
Ittai Abraham and
Shiri Chechik and
Michael Elkin and
Arnold Filtser and
Ofer Neiman Ramsey Spanning Trees and Their
Applications . . . . . . . . . . . . . . 19:1--19:21
Saleh Soltan and
Mihalis Yannakakis and
Gil Zussman Doubly Balanced Connected Graph
Partitioning . . . . . . . . . . . . . . 20:1--20:24
Fedor V. Fomin and
Daniel Lokshtanov and
Sudeshna Kolay and
Fahad Panolan and
Saket Saurabh Subexponential Algorithms for
Rectilinear Steiner Tree and
Arborescence Problems . . . . . . . . . 21:1--21:37
Maria-Florina Balcan and
Nika Haghtalab and
Colin White $k$-center Clustering under Perturbation
Resilience . . . . . . . . . . . . . . . 22:1--22:39
Miriam Backens and
Leslie Ann Goldberg Holant Clones and the Approximability of
Conservative Holant Problems . . . . . . 23:1--23:55
T.-H. Hubert Chan and
Haotian Jiang and
Shaofeng H.-C. Jiang A Unified PTAS for Prize Collecting TSP
and Steiner Tree Problem in Doubling
Metrics . . . . . . . . . . . . . . . . 24:1--24:23
Ivan Bliznets and
Marek Cygan and
Pawe\l Komosa and
Micha\l Pilipczuk and
Lukás Mach Lower Bounds for the Parameterized
Complexity of Minimum Fill-in and Other
Completion Problems . . . . . . . . . . 25:1--25:31
Krzysztof Onak and
Baruch Schieber and
Shay Solomon and
Nicole Wein Fully Dynamic MIS in Uniformly Sparse
Graphs . . . . . . . . . . . . . . . . . 26:1--26:19
Tomasz Kociumaka and
Marcin Kubica and
Jakub Radoszewski and
Wojciech Rytter and
Tomasz Wale\'n A Linear-Time Algorithm for Seeds
Computation . . . . . . . . . . . . . . 27:1--27:23
Sándor Kisfaludi-Bak and
Jesper Nederlof and
Erik Jan van Leeuwen Nearly ETH-tight Algorithms for Planar
Steiner Tree with Terminals on Few Faces 28:1--28:30
Ágnes Cseh and
Tamás Fleiner The Complexity of Cake Cutting with
Unequal Shares . . . . . . . . . . . . . 29:1--29:21
Rodrigo S. V. Martins and
Daniel Panario and
Claudio Qureshi and
Eric Schmutz Periods of Iterations of Functions with
Restricted Preimage Sizes . . . . . . . 30:1--30:28
Achiya Bar-On and
Itai Dinur and
Orr Dunkelman and
Rani Hod and
Nathan Keller and
Eyal Ronen and
Adi Shamir Tight Bounds on Online Checkpointing
Algorithms . . . . . . . . . . . . . . . 31:1--31:22
Daniel Lokshtanov and
Fahad Panolan and
Saket Saurabh and
Roohani Sharma and
Meirav Zehavi Covering Small Independent Sets and
Separators with Applications to
Parameterized Algorithms . . . . . . . . 32:1--32:31
Eden Chlamtác and
Michael Dinitz and
Guy Kortsarz and
Bundit Laekhanukit Approximating Spanners and Directed
Steiner Forest: Upper and Lower Bounds 33:1--33:31
Martin Grohe and
Daniel Neuen and
Pascal Schweitzer and
Daniel Wiebking An Improved Isomorphism Test for
Bounded-tree-width Graphs . . . . . . . 34:1--34:31
André Berger and
László Kozma and
Matthias Mnich and
Roland Vincze Time- and Space-optimal Algorithm for
the Many-visits TSP . . . . . . . . . . 35:1--35:22
Antonio Blanca and
Zongchen Chen and
Daniel Stefankovi\`e and
Eric Vigoda Structure Learning of $H$-Colorings . . 36:1--36:28
Martin E. Dyer and
Andreas Galanis and
Leslie Ann Goldberg and
Mark Jerrum and
Eric Vigoda Random Walks on Small World Networks . . 37:1--37:33
Antonios Antoniadis and
Krzysztof Fleszar and
Ruben Hoeksma and
Kevin Schewior A PTAS for Euclidean TSP with Hyperplane
Neighborhoods . . . . . . . . . . . . . 38:1--38:16
Marthe Bonamy and
Oscar Defrain and
Marc Heinrich and
Micha\l Pilipczuk and
Jean-Florent Raymond Enumerating Minimal Dominating Sets in
Kt-free Graphs and Variants . . . . . . 39:1--39:23
Ori Rottenstreich and
Haim Kaplan and
Avinatan Hassidim Clustering in Hypergraphs to Minimize
Average Edge Service Time . . . . . . . 40:1--40:28
Shay Solomon and
Nicole Wein Improved Dynamic Graph Coloring . . . . 41:1--41:24
Édouard Bonnet and
Tillmann Miltzow Parameterized Hardness of Art Gallery
Problems . . . . . . . . . . . . . . . . 42:1--42:23
Waldo Gálvez and
José A. Soto and
José Verschae Symmetry Exploitation for Online Machine
Covering with Bounded Migration . . . . 43:1--43:22
Surender Baswana and
Keerti Choudhary and
Moazzam Hussain and
Liam Roditty Approximate Single-Source Fault Tolerant
Shortest Path . . . . . . . . . . . . . 44:1--44:22
Josh Alman and
Matthias Mnich and
Virginia Vassilevska Williams Dynamic Parameterized Problems and
Algorithms . . . . . . . . . . . . . . . 45:1--45:46
Deeparnab Chakrabarty and
Prachi Goyal and
Ravishankar Krishnaswamy The Non-Uniform $k$-Center Problem . . . 46:1--46:19
Eduard Eiben and
Iyad Kanj A Colored Path Problem and Its
Applications . . . . . . . . . . . . . . 47:1--47:48
Karl Bringmann and
Pawe\l Gawrychowski and
Shay Mozes and
Oren Weimann Tree Edit Distance Cannot be Computed in
Strongly Subcubic Time (Unless APSP Can) 48:1--48:22
Euiwoong Lee and
Sahil Singla Maximum Matching in the Online
Batch-arrival Model . . . . . . . . . . 49:1--49:31
Johannes Fischer and
Tomohiro I and
Dominik Köppl Deterministic Sparse Suffix Sorting in
the Restore Model . . . . . . . . . . . 50:1--50:53
Akanksha Agrawal and
Daniel Lokshtanov and
Pranabendu Misra and
Saket Saurabh and
Meirav Zehavi Polylogarithmic Approximation Algorithms
for Weighted-$F$-deletion Problems . . . 51:1--51:38
Paul Beame and
Sariel Har-Peled and
Sivaramakrishnan Natarajan Ramamoorthy and
Cyrus Rashtchian and
Makrand Sinha Edge Estimation with Independent Set
Oracles . . . . . . . . . . . . . . . . 52:1--52:27
Johannes Blömer and
Sascha Brauer and
Kathrin Bujna A Complexity Theoretical Study of Fuzzy
$K$-Means . . . . . . . . . . . . . . . 53:1--53:25
Clément Carbonnel and
Miguel Romero and
Stanislav Zivný Point-Width and Max-CSPs . . . . . . . . 54:1--54:28
David G. Harris Oblivious Resampling Oracles and
Parallel Algorithms for the Lopsided
Lovász Local Lemma . . . . . . . . . . . 1:1--1:32
Timothy M. Chan and
R. Ryan Williams Deterministic APSP, Orthogonal Vectors,
and More: Quickly Derandomizing
Razborov--Smolensky . . . . . . . . . . 2:1--2:14
Antje Bjelde and
Jan Hackfeld and
Yann Disser and
Christoph Hansknecht and
Maarten Lipmann and
Julie Meißner and
Miriam SchlÖter and
Kevin Schewior and
Leen Stougie Tight Bounds for Online TSP on the Line 3:1--3:58
Heng Guo and
Chao Liao and
Pinyan Lu and
Chihao Zhang Zeros of Holant Problems: Locations and
Algorithms . . . . . . . . . . . . . . . 4:1--4:25
Mark de Berg and
Kevin Buchin and
Bart M. P. Jansen and
Gerhard Woeginger Fine-grained Complexity Analysis of Two
Classic TSP Variants . . . . . . . . . . 5:1--5:29
Marek Cygan and
Pawe\l Komosa and
Daniel Lokshtanov and
Marcin Pilipczuk and
Micha\l Pilipczuk and
Saket Saurabh and
Magnus Wahlström Randomized Contractions Meet Lean
Decompositions . . . . . . . . . . . . . 6:1--6:30
Nicola Prezza Optimal Substring Equality Queries with
Applications to Sparse Text Indexing . . 7:1--7:23
Anders Roy Christiansen and
Mikko Berggren Ettienne and
Tomasz Kociumaka and
Gonzalo Navarro and
Nicola Prezza Optimal-Time Dictionary-Compressed
Indexes . . . . . . . . . . . . . . . . 8:1--8:39
Sariel Har-Peled and
Mitchell Jones Journey to the Center of the Point Set 9:1--9:21
Gregory Gutin and
Magnus Wahlström and
Meirav Zehavi $r$-Simple $k$-Path and Related Problems
Parameterized by $ k / r$ . . . . . . . 10:1--10:64
Daniel Lokshtanov and
Pranabendu Misra and
Joydeep Mukherjee and
Fahad Panolan and
Geevarghese Philip and
Saket Saurabh $2$-Approximating Feedback Vertex Set in
Tournaments . . . . . . . . . . . . . . 11:1--11:14
Rajesh Chitnis and
Andreas Emil Feldmann and
Pasin Manurangsi Parameterized Approximation Algorithms
for Bidirected Steiner Network Problems 12:1--12:68
Maria Chudnovsky and
Alex Scott and
Paul Seymour Finding a Shortest Odd Hole . . . . . . 13:1--13:21
Chandra Chekuri and
Alina Ene and
Ali Vakilian Node-weighted Network Design in Planar
and Minor-closed Families of Graphs . . 14:1--14:25
Lucas Boczkowski and
Uriel Feige and
Amos Korman and
Yoav Rodeh Navigating in Trees with Permanently
Noisy Advice . . . . . . . . . . . . . . 15:1--15:27
Artur Czumaj and
Peter Davies and
Merav Parter Graph Sparsification for Derandomizing
Massively Parallel Computation with Low
Space . . . . . . . . . . . . . . . . . 16:1--16:27
Magnús M. Halldórsson and
Tigran Tonoyan Sparse Backbone and Optimal Distributed
SINR Algorithms . . . . . . . . . . . . 17:1--17:34
Omar Darwish and
Amr Elmasry and
Jyrki Katajainen Memory-Adjustable Navigation Piles with
Applications to Sorting and Convex Hulls 18:1--18:19
Ali Bibak and
Charles Carlson and
Karthekeyan Chandrasekaran Improving the Smoothed Complexity of
FLIP for Max Cut Problems . . . . . . . 19:1--19:38
Edith Cohen Editorial . . . . . . . . . . . . . . . 19e:1--19e:1
Christian Coester and
Elias Koutsoupias and
Philip Lazos The Infinite Server Problem . . . . . . 20:1--20:23
Caterina Viola and
Stanislav Zivný The Combined Basic LP and Affine IP
Relaxation for Promise VCSPs on Infinite
Domains . . . . . . . . . . . . . . . . 21:1--21:23
Jacob Focke and
Leslie Ann Goldberg and
Stanislav Zivný The Complexity of Approximately Counting
Retractions to Square-free Graphs . . . 22:1--22:51
Yossi Azar and
Arun Ganesh and
Rong Ge and
Debmalya Panigrahi Online Service with Delay . . . . . . . 23:1--23:31
Boris Aronov and
Mark De Berg and
Joachim Gudmundsson and
Michael Horton On $ \beta $-Plurality Points in Spatial
Voting Games . . . . . . . . . . . . . . 24:1--24:21
Karl Bringmann and
Marvin KüNnemann and
André Nusser Discrete Fréchet Distance under
Translation: Conditional Hardness and an
Improved Algorithm . . . . . . . . . . . 25:1--25:42
Daniel Lokshtanov and
Andreas BjÖrklund and
Saket Saurabh and
Meirav Zehavi Approximate Counting of $k$-Paths:
Simpler, Deterministic, and in
Polynomial Space . . . . . . . . . . . . 26:1--26:44
Joshua Brakensiek and
Venkatesan Guruswami The Quest for Strong Inapproximability
Results with Perfect Completeness . . . 27:1--27:35
Guy Even and
Reut Levi and
Moti Medina and
Adi Rosén Sublinear Random Access Generators for
Preferential Attachment Graphs . . . . . 28:1--28:26
Aaron Bernstein and
Sebastian Forster and
Monika Henzinger A Deamortization Approach for Dynamic
Spanner and Dynamic Maximal Matching . . 29:1--29:51
Amir Abboud and
Keren Censor-Hillel and
Seri Khoury and
Ami Paz Smaller Cuts, Higher Lower Bounds . . . 30:1--30:40
Xiaoming Sun and
David P. Woodruff and
Guang Yang and
Jialin Zhang Querying a Matrix through Matrix--Vector
Products . . . . . . . . . . . . . . . . 31:1--31:19
Monaldo Mastrolilli The Complexity of the Ideal Membership
Problem for Constrained Problems Over
the Boolean Domain . . . . . . . . . . . 32:1--32:29
Waldo Gálvez and
Fabrizio Grandoni and
Salvatore Ingala and
Sandy Heydrich and
Arindam Khan and
Andreas Wiese Approximating Geometric Knapsack via
$L$-packings . . . . . . . . . . . . . . 33:1--33:67
Robert E. Tarjan and
Caleb Levy and
Stephen Timmel Zip Trees . . . . . . . . . . . . . . . 34:1--34:12
Hyung-Chan An and
Robert Kleinberg and
David B. Shmoys Approximation Algorithms for the
Bottleneck Asymmetric Traveling Salesman
Problem . . . . . . . . . . . . . . . . 35:1--35:12
Greg Bodwin and
Virginia Vassilevska Williams Better Distance Preservers and Additive
Spanners . . . . . . . . . . . . . . . . 36:1--36:24
Alessandra Graf and
David G. Harris and
Penny Haxell Algorithms for Weighted Independent
Transversals and Strong Colouring . . . 1:1--1:16
Marek Chrobak and
Mordecai Golin and
J. Ian Munro and
Neal E. Young A Simple Algorithm for Optimal Search
Trees with Two-way Comparisons . . . . . 2:1--2:11
Siu-Wing Cheng and
Man-Kit Lau Dynamic Distribution-Sensitive Point
Location . . . . . . . . . . . . . . . . 3:1--3:63
Martin Hoefer and
Tsvi Kopelowitz Introduction to the ACM-SIAM Symposium
on Discrete Algorithms (SODA) 2019
Special Issue . . . . . . . . . . . . . 4e:1--4e:2
Andrzej Grzesik and
Tereza Klimosová and
Marcin Pilipczuk and
Micha\l Pilipczuk Polynomial-time Algorithm for Maximum
Weight Independent Set on $ P_6 $-free
Graphs . . . . . . . . . . . . . . . . . 4:1--4:57
Nairen Cao and
Jeremy T. Fineman and
Katina Russell and
Eugene Yang I/O-Efficient Algorithms for Topological
Sort and Related Problems . . . . . . . 5:1--5:24
Amir Abboud and
Karl Bringmann and
Danny Hermelin and
Dvir Shabtay SETH-based Lower Bounds for Subset Sum
and Bicriteria Path . . . . . . . . . . 6:1--6:22
Alexander Wei Optimal Las Vegas Approximate Near
Neighbors in $ \ell_p $ . . . . . . . . 7:1--7:27
Ruosong Wang and
David P. Woodruff Tight Bounds for $ \ell_1 $ Oblivious
Subspace Embeddings . . . . . . . . . . 8:1--8:32
Yipu Wang Max Flows in Planar Graphs with Vertex
Capacities . . . . . . . . . . . . . . . 9:1--9:27
Sayan Bhattacharya and
Fabrizio Grandoni and
Janardhan Kulkarni and
Quanquan C. Liu and
Shay Solomon Fully Dynamic $ (\Delta + 1) $-Coloring
in $ O(1) $ Update Time . . . . . . . . 10:1--10:25
Édouard Bonnet 4 vs 7 Sparse Undirected Unweighted
Diameter Is SETH-hard at Time $ n^{4 /
3} $ . . . . . . . . . . . . . . . . . . 11:1--11:14
John Haslegrave and
Thomas Sauerwald and
John Sylvester Time Dependent Biased Random Walks . . . 12:1--12:30
Dániel Marx and
Micha\l Pilipczuk Optimal Parameterized Algorithms for
Planar Facility Location Problems Using
Voronoi Diagrams . . . . . . . . . . . . 13:1--13:64
Sergio Cabello Computing the Inverse Geodesic Length in
Planar Graphs and Graphs of Bounded
Treewidth . . . . . . . . . . . . . . . 14:1--14:26
Magnus Wahlström Quasipolynomial Multicut-mimicking
Networks and Kernels for Multiway Cut
Problems . . . . . . . . . . . . . . . . 15:1--15:19
Monika Henzinger and
Pan Peng Constant-time Dynamic $ (\Delta + 1)
$-Coloring . . . . . . . . . . . . . . . 16:1--16:21
Marek Cygan and
Jesper Nederlof and
Marcin Pilipczuk and
Micha\l Pilipczuk and
Johan M. M. Van Rooij and
Jakub Onufry Wojtaszczyk Solving Connectivity Problems
Parameterized by Treewidth in Single
Exponential Time . . . . . . . . . . . . 17:1--17:31
Panagiotis Charalampopoulos and
Shay Mozes and
Benjamin Tebeka Exact Distance Oracles for Planar Graphs
with Failing Vertices . . . . . . . . . 18:1--18:23
Thomas Bläsius and
Cedric Freiberger and
Tobias Friedrich and
Maximilian Katzmann and
Felix Montenegro-Retana and
Marianne Thieffry Efficient Shortest Paths in Scale-Free
Networks with Underlying Hyperbolic
Geometry . . . . . . . . . . . . . . . . 19:1--19:32
Joachim Gudmundsson and
Sampson Wong Improving the Dilation of a Metric Graph
by Adding Edges . . . . . . . . . . . . 20:1--20:??
Ignasi Sau and
Giannos Stamoulis and
Dimitrios M. Thilikos $k$-apices of Minor-closed Graph
Classes. II. Parameterized Algorithms 21:1--21:??
Pak Hay Chan and
Lap Chi Lau and
Aaron Schild and
Sam Chiu-Wai Wong and
Hong Zhou Network Design for $ s - t $ Effective
Resistance . . . . . . . . . . . . . . . 22:1--22:??
John Fearnley and
Dömötör Pálvölgyi and
Rahul Savani A Faster Algorithm for Finding Tarski
Fixed Points . . . . . . . . . . . . . . 23:1--23:??
Antonio Boffa and
Paolo Ferragina and
Giorgio Vinciguerra A Learned Approach to Design Compressed
Rank/Select Data Structures . . . . . . 24:1--24:??
Avery Miller and
Andrzej Pelc and
Ram Narayan Yadav Deterministic Leader Election in
Anonymous Radio Networks . . . . . . . . 25:1--25:??
Pankaj K. Agarwal and
Ravid Cohen and
Dan Halperin and
Wolfgang Mulzer Maintaining the Union of Unit Discs
under Insertions with Near-Optimal
Overhead . . . . . . . . . . . . . . . . 26:1--26:??
Daniel Neuen Hypergraph Isomorphism for Groups with
Restricted Composition Factors . . . . . 27:1--27:??
Weiming Feng and
Heng Guo and
Yitong Yin and
Chihao Zhang Rapid Mixing from Spectral Independence
beyond the Boolean Domain . . . . . . . 28:1--28:??
Kai Jin and
Siu-Wing Cheng and
Man-Kwun Chiu and
Man Ting Wong A Generalization of Self-Improving
Algorithms . . . . . . . . . . . . . . . 29:1--29:??
Gautam Kamath and
Sepehr Assadi and
Anne Driemel and
Janardhan Kulkarni Introduction to the Special Issue on
ACM-SIAM Symposium on Discrete
Algorithms (SODA) 2020 . . . . . . . . . 30:1--30:??
Xi Chen and
Tim Randolph and
Rocco A. Servedio and
Timothy Sun A Lower Bound on Cycle-Finding in Sparse
Digraphs . . . . . . . . . . . . . . . . 31:1--31:??
Matthew Joseph and
Jieming Mao and
Aaron Roth Exponential Separations in Local Privacy 32:1--32:??
Sepehr Abbasi-Zadeh and
Nikhil Bansal and
Guru Guruganesh and
Aleksandar Nikolov and
Roy Schwartz and
Mohit Singh Sticky Brownian Rounding and its
Applications to Constraint Satisfaction
Problems . . . . . . . . . . . . . . . . 33:1--33:??
Jason Li and
Jesper Nederlof Detecting Feedback Vertex Sets of Size
$k$ in $ O^\star (2.7 k)$ Time . . . . . 34:1--34:??
Rahul Arya and
Sunil Arya and
Guilherme D. da Fonseca and
David Mount Optimal Bound on the Combinatorial
Complexity of Approximating Polytopes 35:1--35:??
Hsien-Chih Chang and
Arnaud de Mesmay Tightening Curves on Surfaces
Monotonically with Applications . . . . 36:1--36:??
Piotr Berman and
Meiram Murzabulatov and
Sofya Raskhodnikova Tolerant Testers of Image Properties . . 37:1--37:??
Saladi Rahul and
Yufei Tao Generic Techniques for Building Top-$k$
Structures . . . . . . . . . . . . . . . 38:1--38:??
Zhihao Jiang and
Debmalya Panigrahi and
Kevin Sun Online Algorithms for Weighted Paging
with Predictions . . . . . . . . . . . . 39:1--39:??
Pankaj Agarwal and
Hsien-Chih Chang and
Subhash Suri and
Allen Xiao and
Jie Xue Dynamic Geometric Set Cover and Hitting
Set . . . . . . . . . . . . . . . . . . 40:1--40:??
Erez Kantor and
Zvi Lotker and
Merav Parter and
David Peleg The Minimum Principle of SINR: a Useful
Discretization Tool for Wireless
Communication . . . . . . . . . . . . . 1:1--1:??
Lior Gishboliner and
Yevgeny Levanzov and
Asaf Shapira and
Raphael Yuster Counting Homomorphic Cycles in
Degenerate Graphs . . . . . . . . . . . 2:1--2:??
Amir Abboud and
Fabrizio Grandoni and
Virginia Vassilevska Williams Subcubic Equivalences between Graph
Centrality Problems, APSP, and Diameter 3:1--3:??
Maike Buchin and
Anne Driemel and
Dennis Rohde Approximating $ (k, l)$-Median
Clustering for Polygonal Curves . . . . 4:1--4:??
Rahul Shah and
Cheng Sheng and
Sharma Thankachan and
Jeffrey Vitter Ranked Document Retrieval in External
Memory . . . . . . . . . . . . . . . . . 5:1--5:??
Takehiro Ito and
Yuni Iwamasa and
Naonori Kakimura and
Naoyuki Kamiyama and
Yusuke Kobayashi and
Shun-Ichi Maezawa and
Yuta Nozaki and
Yoshio Okamoto and
Kenta Ozeki Monotone Edge Flips to an Orientation of
Maximum Edge-Connectivity \`a la
Nash--Williams . . . . . . . . . . . . . 6:1--6:??
Sariel Har-Peled and
Manor Mendel and
Dániel Oláh Reliable Spanners for Metric Spaces . . 7:1--7:??
Nikhil Bansal and
Marek Eliás and
Grigorios Koumoutsos and
Jesper Nederlof Competitive Algorithms for Generalized
$k$-Server in Uniform Metrics . . . . . 8:1--8:??
Karl Bringmann and
Vincent Cohen-Addad and
Debarati Das A Linear-Time $ n^{0.4}$-Approximation
for Longest Common Subsequence . . . . . 9:1--9:??
Franziska Eberle and
Nicole Megow and
Kevin Schewior Online Throughput Maximization on
Unrelated Machines: Commitment is No
Burden . . . . . . . . . . . . . . . . . 10:1--10:??
Akanksha Agrawal and
Daniel Lokshtanov and
Pranabendu Misra and
Saket Saurabh and
Meirav Zehavi Polynomial Kernel for Interval Vertex
Deletion . . . . . . . . . . . . . . . . 11:1--11:??
Arun Ganesh and
Bruce M. Maggs and
Debmalya Panigrahi Robust Algorithms for TSP and Steiner
Tree . . . . . . . . . . . . . . . . . . 12:1--12:??
Kyle Fox and
Debmalya Panigrahi and
Fred Zhang Minimum Cut and Minimum $k$-Cut in
Hypergraphs via Branching Contractions 13:1--13:??
Balázs F. Mezei and
Marcin Wrochna and
stanislav Zivný PTAS for Sparse General-valued CSPs . . 14:1--14:??
Arun Ganesh and
Bruce M. Maggs and
Debmalya Panigrahi Universal Algorithms for Clustering
Problems . . . . . . . . . . . . . . . . 15:1--15:??
Carla Groenland and
Gwenaël Joret and
Wojciech Nadara and
Bartosz Walczak Approximating Pathwidth for Graphs of
Small Treewidth . . . . . . . . . . . . 16:1--16:??
Claire Mathieu and
Hang Zhou A PTAS for Capacitated Vehicle Routing
on Trees . . . . . . . . . . . . . . . . 17:1--17:??
Varun Kanade and
Frederik Mallmann-Trenn and
Thomas Sauerwald On Coalescence Time in Graphs: When Is
Coalescing as Fast as Meeting? . . . . . 18:1--18:??
Antonios Antoniadis and
Christian Coester and
Marek Eliás and
Adam Polak and
Bertrand Simon Online Metric Algorithms with Untrusted
Predictions . . . . . . . . . . . . . . 19:1--19:??
Aditya Jayaprakash and
Mohammad R. Salavatipour Approximation Schemes for Capacitated
Vehicle Routing on Graphs of Bounded
Treewidth, Bounded Doubling, or Highway
Dimension . . . . . . . . . . . . . . . 20:1--20:??
Massimo Equi and
Veli Mäkinen and
Alexandru I. Tomescu and
Roberto Grossi On the Complexity of String Matching for
Graphs . . . . . . . . . . . . . . . . . 21:1--21:??
Sébastien Bouchard and
Yoann Dieudonné and
Arnaud Labourel and
Andrzej Pelc Almost-Optimal Deterministic Treasure
Hunt in Unweighted Graphs . . . . . . . 22:1--22:??
Petr A. Golovach and
Giannos Stamoulis and
Dimitrios M. Thilikos Hitting Topological Minor Models in
Planar Graphs is Fixed Parameter
Tractable . . . . . . . . . . . . . . . 23:1--23:??
Stefan Walzer Load Thresholds for Cuckoo Hashing with
Overlapping Blocks . . . . . . . . . . . 24:1--24:??
Prosenjit Bose and
Jean Cardinal and
John Iacono and
Grigorios Koumoutsos and
Stefan Langerman Competitive Online Search Trees on Trees 25:1--25:??
Marco Bressan Efficient and Near-optimal Algorithms
for Sampling Small Connected Subgraphs 26:1--26:??
Rajesh Jayaram and
David P. Woodruff Towards Optimal Moment Estimation in
Streaming and Distributed Models . . . . 27:1--27:??
Enoch Peserico and
Michele Scquizzato Matching on the Line Admits no $ o(\sqrt
{\log n})$-Competitive Algorithm . . . . 28:1--28:??
Kevin Buchin and
Chenglin Fan and
Maarten Löffler and
Aleksandr Popov and
Benjamin Raichel and
Marcel Roeloffzen Fréchet Distance for Uncertain Curves . . 29:1--29:??
Anders Aamand and
Mikkel Abrahamsen and
Peter M. R. Rasmussen and
Thomas D. Ahle Tiling with Squares and Packing Dominos
in Polynomial Time . . . . . . . . . . . 30:1--30:??
Argyrios Deligkas and
Michail Fasoulakis and
Evangelos Markakis A Polynomial-Time Algorithm for $ 1 /
3$-Approximate Nash Equilibria in
Bimatrix Games . . . . . . . . . . . . . 31:1--31:??
Philip Bille and
Inge Li Gòrtz and
Teresa Anna Steiner String Indexing with Compressed Patterns 32:1--32:??
Yi-Jun Chang and
Ran Duan and
Shunhua Jiang Near-Optimal Time-Energy Tradeoffs for
Deterministic Leader Election . . . . . 33:1--33:??
Thomas Bläsius and
Simon D. Fink and
Ignaz Rutter Synchronized Planarity with Applications
to Constrained Planarity Problems . . . 34:1--34:??
Manuel Lafond Recognizing $k$-Leaf Powers in
Polynomial Time, for Constant $k$ . . . 35:1--35:??
Jugal Garg and
Pooja Kulkarni and
Rucha Kulkarni Approximating Nash Social Welfare under
Submodular Valuations through
(Un)Matchings . . . . . . . . . . . . . 36:1--36:??
Stavros Birmpilis and
George Labahn and
Arne Storjohann A Cubic Algorithm for Computing the
Hermite Normal Form of a Nonsingular
Integer Matrix . . . . . . . . . . . . . 37:1--37:??
Surender Baswana and
Koustav Bhanja and
Abhyuday Pandey Minimum+1 $ (s, t)$-cuts and Dual-edge
Sensitivity Oracle . . . . . . . . . . . 38:1--38:??
Arnold Filtser and
Omrit Filtser Static and Streaming Data Structures for
Fréchet Distance Queries . . . . . . . . 39:1--39:??
Eden Pelleg and
Stanislav Zivný Additive Sparsification of CSPs . . . . 1:1--1:??
Fedor V. Fomin and
Petr A. Golovach and
Tuukka Korhonen and
Daniel Lokshtanov and
Giannos Stamoulis Shortest Cycles with Monotone Submodular
Costs . . . . . . . . . . . . . . . . . 2:1--2:??
Shaohua Li and
Marcin Pilipczuk and
Manuel Sorge Cluster Editing Parameterized above
Modification-disjoint $ P_3 $-packings 3:1--3:??
Massimo Cairo and
Romeo Rizzi and
Alexandru I. Tomescu and
Elia C. Zirondelli Genome Assembly, from Practice to
Theory: Safe, Complete and Linear-Time 4:1--4:??
Antonio Blanca and
Sarah Cannon and
Will Perkins Fast and Perfect Sampling of Subgraphs
and Polymer Systems . . . . . . . . . . 5:1--5:??
Parinya Chalermsook and
Matthias Kaul and
Matthias Mnich and
Joachim Spoerhase and
Sumedha Uniyal and
Daniel Vaz Approximating Sparsest Cut in
Low-treewidth Graphs via Combinatorial
Diameter . . . . . . . . . . . . . . . . 6:1--6:??
Ivona Bezáková and
Andreas Galanis and
Leslie Ann Goldberg and
Daniel Stefankovic Fast Sampling via Spectral Independence
Beyond Bounded-degree Graphs . . . . . . 7:1--7:??
Telikepalli Kavitha Popular Matchings with One-Sided Bias 8:1--8:??
Lars Gottesbüren and
Tobias Heuer and
Nikolai Maas and
Peter Sanders and
Sebastian Schlag Scalable High-Quality Hypergraph
Partitioning . . . . . . . . . . . . . . 9:1--9:??
Thomas Bläsius and
Philipp Fischbeck On the External Validity of Average-case
Analyses of Graph Algorithms . . . . . . 10:1--10:??
Jacob Focke and
Dániel Marx and
Pawe\l Rzazewski Counting List Homomorphisms from Graphs
of Bounded Treewidth: Tight Complexity
Bounds . . . . . . . . . . . . . . . . . 11:1--11:??
Eun Jung Kim and
Stefan Kratsch and
Marcin Pilipczuk and
Magnus Wahlström Flow-augmentation II: Undirected Graphs 12:1--12:??
Manuel Cáceres and
Massimo Cairo and
Andreas Grigorjew and
Shahbaz Khan and
Brendan Mumey and
Romeo Rizzi and
Alexandru I. Tomescu and
Lucia Williams Width Helps and Hinders Splitting Flows 13:1--13:??
Joachim Gudmundsson and
Martin P. Seybold and
Sampson Wong Map Matching Queries on Realistic Input
Graphs Under the Fréchet Distance . . . . 14:1--14:??
Fahad Panolan and
Saket Saurabh and
Meirav Zehavi Contraction Decomposition in Unit Disk
Graphs and Algorithmic Applications in
Parameterized Complexity . . . . . . . . 15:1--15:??
Arturo Merino and
Andreas Wiese On the Two-Dimensional Knapsack Problem
for Convex Polygons . . . . . . . . . . 16:1--16:??
Niclas Boehmer and
Tomohiro Koana The Complexity of Finding Fair
Many-to-One Matchings . . . . . . . . . 17:1--17:??
Jannik Olbrich and
Enno Ohlebusch and
Thomas Büchler Generic Non-recursive Suffix Array
Construction . . . . . . . . . . . . . . 18:1--18:??
Robert Ganian and
Thekla Hamm and
Viktoriia Korchemna and
Karolina Okrasa and
Kirill Simonov The Fine-Grained Complexity of Graph
Homomorphism Parameterized by
Clique-Width . . . . . . . . . . . . . . 19:1--19:??
Sayan Bandyapadhyay and
William Lochet and
Daniel Lokshtanov and
Saket Saurabh and
Jie Xue True Contraction Decomposition and
Almost ETH-Tight Bipartization for
Unit-Disk Graphs . . . . . . . . . . . . 20:1--20:??
Daniel Dadush and
Martin Milanic and
Tami Tamir Introduction: ACM-SIAM Symposium on
Discrete Algorithms (SODA) 2022 Special
Issue . . . . . . . . . . . . . . . . . 21:1--21:??
Kim-Manuel Klein and
Janina Reuter Collapsing the Tower-On the Complexity
of Multistage Stochastic IPs . . . . . . 22:1--22:??
Hung Le and
Cuong Than Greedy Spanners in Euclidean Spaces
Admit Sublinear Separators . . . . . . . 23:1--23:??
Timothy M. Chan and
Da Wei Zheng Hopcroft's Problem, Log* Shaving,
Two-dimensional Fractional Cascading,
and Decision Trees . . . . . . . . . . . 24:1--24:??
Daniel Neuen Isomorphism Testing for Graphs Excluding
Small Topological Subgraphs . . . . . . 25:1--25:??
Dvir Fried and
Shay Golan and
Tomasz Kociumaka and
Tsvi Kopelowitz and
Ely Porat and
Tatiana Starikovskaya An Improved Algorithm for the $k$-Dyck
Edit Distance Problem . . . . . . . . . 26:1--26:??
Lorenzo Beretta and
Jakub Tetek Better Sum Estimation via Weighted
Sampling . . . . . . . . . . . . . . . . 27:1--27:??
Artur Czumaj and
Shaofeng H.-C. Jiang and
Robert Krauthgamer and
Pavel Veselý Streaming Algorithms for Geometric
Steiner Forest . . . . . . . . . . . . . 28:1--28:??
Jacobus Conradi and
Anne Driemel On Computing the $k$-Shortcut Fréchet
Distance . . . . . . . . . . . . . . . . 29:1--29:??
Arnold Filtser Scattering and Sparse Partitions, and
Their Applications . . . . . . . . . . . 30:1--30:??
Vincent Jugé Adaptive Shivers Sort: an Alternative
Sorting Algorithm . . . . . . . . . . . 31:1--31:55
Ce Jin and
Jakob Nogler Quantum Speed-Ups for String
Synchronizing Sets, Longest Common
Substring, and $k$-mismatch Matching . . 32:1--32:??
Tamio-Vesa Nakajima and
Stanislav Zivný On the Complexity of Symmetric vs.
Functional PCSPs . . . . . . . . . . . . 33:1--33:??
Karthik C. S. and
Merav Parter Deterministic Replacement Path Covering 34:1--34:??
Dimitrios Los and
Thomas Sauerwald An Improved Drift Theorem for Balanced
Allocations . . . . . . . . . . . . . . 35:1--35:??
Fedor V. Fomin and
Petr A. Golovach and
Tuukka Korhonen and
Kirill Simonov and
Giannos Stamoulis Fixed-Parameter Tractability of Maximum
Colored Path and Beyond . . . . . . . . 36:1--36:??
Claire Mathieu and
Rajmohan Rajaraman and
Neal E. Young and
Arman Yousefi Competitive Data-Structure Dynamization 37:1--37:??
Antonios Antoniadis and
Matthias Englert and
Nicolaos Matsakis and
Pavel Veselý Breaking the Barrier of 2 for the
Competitiveness of Longest Queue Drop 38:1--38:??