default search action
28th SODA 2017: Barcelona, Spain
- Philip N. Klein:
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. SIAM 2017, ISBN 978-1-61197-478-2 - Front Matter.
- Sariel Har-Peled, Sepideh Mahabadi:
Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search. 1-15 - Georgia Avarikioti, Ioannis Z. Emiris, Loukas Kavouras, Ioannis Psarros:
High-dimensional approximate r-nets. 16-30 - Tobias Christiani:
A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering. 31-46 - Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten:
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. 47-66 - Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki:
LSH Forest: Practical Algorithms Made Theoretical. 67-78 - Sandy Heydrich, Andreas Wiese:
Faster approximation schemes for the two-dimensional knapsack problem. 79-98 - Sebastian Morr:
Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density. 99-109 - Lingxiao Huang, Jian Li:
Stochastic k-Center and j-Flat-Center Problems. 110-129 - Alfonso Cevallos, Friedrich Eisenbrand, Rico Zenklusen:
Local Search for Max-Sum Diversification. 130-142 - László Kozma, Tobias Mömke:
Maximum Scatter TSP in Doubling Metrics. 143-153 - Rafail Ostrovsky, Yuval Rabani, Arman Yousefi:
Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration. 154-169 - Igor Potapov, Pavel Semukhin:
Decidability of the Membership Problem for 2 × 2 integer matrices. 170-186 - Paul C. Bell, Mika Hirvensalo, Igor Potapov:
The Identity Problem for Matrix Semigroups in SL2(ℤ) is NP-complete. 187-206 - Lihi Cohen, Yuval Emek, Oren Louidor, Jara Uitto:
Exploring an Infinite Space with Finite Memory Scouts. 207-224 - Cameron T. Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert T. Schweller, Luis Vega, Tim Wylie:
Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces. 225-238 - Thomas D. Ahle, Martin Aumüller, Rasmus Pagh:
Parameter-free Locality Sensitive Hashing for Spherical Range Reporting. 239-256 - Mayank Goswami, Rasmus Pagh, Francesco Silvestri, Johan Sivertsen:
Distance Sensitive Bloom Filters Without False Negatives. 257-269 - Sunil Arya, Guilherme Dias da Fonseca, David M. Mount:
Optimal Approximate Polytope Membership. 270-288 - Paul Beame, Cyrus Rashtchian:
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube. 289-306 - Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek:
Even Delta-Matroids and the Complexity of Planar Boolean CSPs. 307-326 - Christoph Berkholz, Martin Grohe:
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism. 327-339 - Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal:
Robust algorithms with polynomial loss for near-unanimity CSPs. 340-357 - Xue Chen, Yuan Zhou:
Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints. 358-377 - Vít Jelínek, Jan Kyncl:
Hardness of Permutation Pattern Matching. 378-396 - Arnab Ganguly, Rahul Shah, Sharma V. Thankachan:
pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems. 397-407 - J. Ian Munro, Gonzalo Navarro, Yakov Nekrich:
Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time. 408-424 - Pawel Gawrychowski, Tomasz Kociumaka:
Sparse Suffix Tree Construction in Optimal Time and Space. 425-439 - Ittai Abraham, Shiri Chechik, Sebastian Krinninger:
Fully dynamic all-pairs shortest paths with worst-case update-time revisited. 440-452 - Aaron Bernstein, Shiri Chechik:
Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs. 453-469 - Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai:
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time. 470-489 - Ran Duan, Seth Pettie:
Connectivity Oracles for Graphs Subject to Vertex Failures. 490-509 - Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie:
Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time. 510-520 - Paul Dütting, Thomas Kesselheim:
Best-Response Dynamics in Combinatorial Auctions with Item Bidding. 521-533 - Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit:
Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. 534-553 - Krishnamurthy Dvijotham, Yuval Rabani, Leonard J. Schulman:
Convergence of Incentive-Driven Dynamics in Fisher Markets. 554-567 - Amir Abboud, Greg Bodwin, Seth Pettie:
A Hierarchy of Lower Bounds for Sublinear Additive Spanners. 568-576 - Alberto Del Pia, Michael Ferris, Carla Michini:
Totally Unimodular Congestion Games. 577-588 - Anupam Gupta, R. Ravi, Kunal Talwar, Seeun William Umboh:
LAST but not Least: Online Spanners for Buy-at-Bulk. 589-599 - Greg Bodwin:
Linear Size Distance Preservers. 600-615 - Yu Cheng, Ilias Diakonikolas, Alistair Stewart:
Playing Anonymous Games using Simple Strategies. 616-631 - Renato Paes Leme, Sam Chiu-wai Wong:
Computing Walrasian Equilibria: Fast Algorithms and Structural Properties. 632-651 - Michael Elkin, Ofer Neiman:
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. 652-669 - Anastasios Sidiropoulos, Dingkang Wang, Yusu Wang:
Metric embeddings with outliers. 670-689 - Assaf Naor:
Probabilistic clustering of high dimensional norms. 690-709 - Piotr Indyk, Tal Wagner:
Near-Optimal (Euclidean) Metric Compression. 710-723 - Amir Nayyeri, Benjamin Raichel:
A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs. 724-736 - Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Daniel Vaz:
Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs. 737-751 - Michael B. Cohen, Aleksander Madry, Piotr Sankowski, Adrian Vladu:
Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ (m10/7 log W) Time (Extended Abstract). 752-771 - Jonah Sherman:
Generalized Preconditioning and Undirected Minimum-Cost Flow. 772-780 - Ran Duan, Seth Pettie, Hsin-Hao Su:
Scaling Algorithms for Weighted Matching in General Graphs. 781-800 - Chandra Chekuri, Kent Quanrud:
Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems. 801-820 - Miriam Schlöter, Martin Skutella:
Fast and Memory-Efficient Algorithms for Evacuation Problems. 821-840 - Moses Charikar, Vaggos Chatziafratis:
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics. 841-854 - Chandra Chekuri, Vivek Madan:
Approximating Multicut and the Demand Graph. 855-874 - Yixin Cao, R. B. Sandeep:
Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds. 875-880 - Eden Chlamtác, Michael Dinitz, Yury Makarychev:
Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. 881-899 - Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan:
Approximation Algorithms for Label Cover and The Log-Density Threshold. 900-919 - Michele Borassi, Pierluigi Crescenzi, Luca Trevisan:
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. 920-939 - Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Find Your Place: Simple Distributed Algorithms for Community Detection. 940-959 - Aviad Rubinstein, Shai Vardi:
Sorting from Noisier Samples. 960-972 - Uri Grupel:
Sampling on the Sphere by Mutually Orthogonal Subspaces. 973-983 - Nicole Immorlica, Robert Kleinberg, Brendan Lucier, Morteza Zadomighaddam:
Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals. 984-993 - Antje Bjelde, Yann Disser, Jan Hackfeld, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Kevin Schewior, Miriam Schlöter, Leen Stougie:
Tight Bounds for Online TSP on the Line. 994-1005 - George Christodoulou, Alkmini Sgouritsa:
An Improved Upper Bound for the Universal TSP on the Grid. 1006-1021 - Nikhil Bansal, Marek Eliás, Lukasz Jez, Grigorios Koumoutsos:
The (h, k)-Server Problem on Bounded Depth Trees. 1022-1037 - Yossi Azar, Ilan Reuven Cohen, Alan Roytman:
Online Lower Bounds via Duality. 1038-1050 - Yossi Azar, Ashish Chiplunkar, Haim Kaplan:
Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays. 1051-1061 - Konstantinos Koiliaris, Chao Xu:
A Faster Pseudopolynomial Time Algorithm for Subset Sum. 1062-1072 - Karl Bringmann:
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. 1073-1084 - Chandra Chekuri, Chao Xu:
Computing minimum cuts in hypergraphs. 1085-1100 - Mohsen Ghaffari, David R. Karger, Debmalya Panigrahi:
Random Contractions and Sampling for Hypergraph and Hedge Connectivity. 1101-1114 - Akshay Ramachandran, Aaron Schild:
Sandpile prediction on a tree in near linear time. 1115-1131 - Raghu Meka:
Explicit Resilient Functions Matching Ajtai-Linial. 1132-1148 - Noga Alon, Rajko Nenadov:
Optimal induced universal graphs for bounded-degree graphs. 1149-1157 - Shayan Oveis Gharan, Alireza Rezaei:
Approximation Algorithms for Finding Maximum Induced Expanders. 1158-1169 - Bernhard Haeupler, David G. Harris:
Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs. 1170-1187 - David G. Harris:
Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma. 1188-1203 - T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang:
Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids. 1204-1223 - Matthias Englert, Harald Räcke:
Reordering Buffers with Logarithmic Diameter Dependency for Trees. 1224-1234 - Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Ohad Talmon:
O(depth)-Competitive Algorithm for Online Multi-level Aggregation. 1235-1244 - Xi Chen, Sivakanth Gopi, Jieming Mao, Jon Schneider:
Competitive analysis of the top-K ranking problem. 1245-1264 - Vitaly Feldman, Cristóbal Guzmán, Santosh S. Vempala:
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization. 1265-1277 - Jayadev Acharya, Ilias Diakonikolas, Jerry Li, Ludwig Schmidt:
Sample-Optimal Density Estimation in Nearly-Linear Time. 1278-1289 - Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, James Worrell:
On Rationality of Nonnegative Matrix Factorization. 1290-1305 - Mark Bun, Thomas Steinke, Jonathan R. Ullman:
Make Up Your Mind: The Price of Online Queries in Differential Privacy. 1306-1325 - Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-k-Subgraph with Perfect Completeness. 1326-1341 - Frédéric Meunier, Wolfgang Mulzer, Pauline Sarrabezolles, Yannik Stein:
The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications. 1342-1351 - Pavel Hubácek, Eylon Yogev:
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. 1352-1371 - Daniel Prusa, Tomás Werner:
LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP. 1372-1382 - Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi:
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion. 1383-1398 - Bart M. P. Jansen, Marcin Pilipczuk:
Approximation and Kernelization for Chordal Vertex Deletion. 1399-1418 - Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, Marcin Wrochna:
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. 1419-1432 - Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh:
Spanning Circuits in Regular Matroids. 1433-1441 - Haris Angelidakis, Yury Makarychev, Vsevolod Oparin:
Algorithmic and Hardness Results for the Hub Labeling Problem. 1442-1461 - Adrian Kosowski, Laurent Viennot:
Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. 1462-1478 - Shiri Chechik, Sarel Cohen, Amos Fiat, Haim Kaplan:
(1 + ∊)-Approximate f-Sensitive Distance Oracles. 1479-1496 - Alan M. Frieze, Tony Johansson:
On the insertion time of random walk cuckoo hashing. 1497-1502 - Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Tsvi Kopelowitz, Pablo Montes:
File Maintenance: When in Doubt, Change the Layout! 1503-1522 - Peyman Afshani, Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Mayank Goswami, Meng-Tsung Tsai:
Cross-Referenced Dictionaries and the Limits of Write Optimization. 1523-1532 - Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz:
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes. 1533-1545 - Euiwoong Lee:
Partitioning a Graph into Small Pieces with Applications to Path Transversal. 1546-1558 - Magnus Wahlström:
LP-branching algorithms based on biased graphs. 1559-1570 - Klaus Jansen, Kim-Manuel Klein:
About the Structure of the Integer Cone and its Application to Bin Packing. 1571-1581 - Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler:
Testing for Forbidden Order Patterns in an Array. 1582-1597 - Aram W. Harrow, Cedric Yen-Yu Lin, Ashley Montanaro:
Sequential measurements, disturbance and property testing. 1598-1611 - Jacob Fox, László Miklós Lovász:
A tight bound for Green's arithmetic triangle removal lemma in vector spaces. 1612-1617 - Jacob Fox, Fan Wei:
Permutation Property Testing under Different Metrics with Low Query Complexity. 1618-1637 - Marco Molinaro:
Online and Random-order Load Balancing Simultaneously. 1638-1650 - Moran Feldman, Rani Izsak:
Building a Good Team: Secretary Problems and the Supermodular Degree. 1651-1670 - Aviad Rubinstein, Sahil Singla:
Combinatorial Prophet Inequalities. 1671-1687 - Anupam Gupta, Viswanath Nagarajan, Sahil Singla:
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions. 1688-1702 - Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker:
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. 1703-1722 - Sepehr Assadi, Sanjeev Khanna, Yang Li:
On Estimating Maximum Matching Size in Graph Streams. 1723-1742 - Themistoklis Gouleakis, Christos Tzamos, Manolis Zampetakis:
Faster Sublinear Algorithms using Conditional Sampling. 1743-1757 - Michael B. Cohen, Cameron Musco, Christopher Musco:
Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling. 1758-1777 - John Kallaugher, Eric Price:
A Hybrid Sampling Scheme for Triangle Counting. 1778-1797 - Pinyan Lu, Kuan Yang, Chihao Zhang, Minshen Zhu:
An FPTAS for Counting Proper Four-Colorings on Cubic Graphs. 1798-1817 - Heng Guo, Mark Jerrum:
Random cluster dynamics for the Ising model is rapidly mixing. 1818-1827 - Prateek Bhakta, Ben Cousins, Matthew Fahrbach, Dana Randall:
Approximately Sampling Elements with Fixed Rank in Graded Posets. 1828-1838 - Roee David, Uriel Feige:
Random Walks with the Minimum Degree Local Rule Have O(N2) Cover Time. 1839-1848 - Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau:
Random Walks and Evolving Sets: Faster Convergences and Limitations. 1849-1865 - James B. Orlin, Antonio Sedeño-Noda:
An O(nm) time algorithm for finding the min length directed cycle in a graph. 1866-1879