default search action
25th SODA 2014: Portland, Oregon, USA
- Chandra Chekuri:
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014. SIAM 2014, ISBN 978-1-61197-338-9 - MohammadTaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha:
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median. 1-12 - Nikhil Bansal, Arindam Khan:
Improved Approximation Algorithm for Two-Dimensional Bin Packing. 13-25 - Aris Anagnostopoulos, Fabrizio Grandoni
, Stefano Leonardi, Andreas Wiese:
A Mazing 2+∊ Approximation for Unsplittable Flow on a Path. 26-41 - Marcin Bienkowski
Better Approximation Bounds for the Joint Replenishment Problem. 42-54 - Nikhil Bansal, Moses Charikar
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach. 55-71 - Ken-ichi Kawarabayashi, Stephan Kreutzer:
An Excluded Grid Theorem for Digraphs with Forbidden Minors. 72-81 - Sylvain Guillemot, Dániel Marx:
Finding small patterns in permutations in linear time. 82-101 - Laurent Bulteau
Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable. 102-121 - Yixin Cao, Dániel Marx:
Interval Deletion is Fixed-Parameter Tractable. 122-141 - Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh:
Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. 142-151 - Herbert Edelsbrunner, Salman Parsa:
On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank. 152-160 - Siu-Wing Cheng, Man-Kwun Chiu:
Implicit Manifold Reconstruction. 161-173 - Primoz Skraba, Bei Wang:
Approximating Local Homology from Samples. 174-192 - Peter Franek, Marek Krcál:
Robust Satisfiability of Systems of Equations. 193-203 - Michael B. Cohen
Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball. 204-216 - Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford:
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. 217-226 - Harald Räcke, Chintan Shah, Hanjo Täubig:
Computing Cut-Based Hierarchical Decompositions in Almost Linear Time. 227-238 - Kook Jin Ahn, Sudipto Guha:
Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b-Matching Problems in Nonbipartite Graphs. 239-258 - David G. Harris, Aravind Srinivasan:
Improved bounds and algorithms for graph cuts and network reliability. 259-278 - Alexandr Andoni, Anupam Gupta, Robert Krauthgamer:
Towards (1 + ∊)-Approximate Flow Sparsifiers. 279-293 - Enrica Duchi, Dominique Poulalhon, Gilles Schaeffer:
Uniform random sampling of simple branched coverings of the sphere by itself. 294-304 - Charilaos Efthymiou:
MCMC sampling colourings and independent sets of G(n, d/n) near uniqueness threshold. 305-316 - Pu Gao, Xavier Pérez-Giménez
Arboricity and spanning-tree packing in random graphs with an application to load balancing. 317-326 - Prateek Bhakta, Sarah Miracle, Dana Randall:
Clustering and Mixing Times for Segregation Models on ℤ2. 327-340 - Chengyu Lin
A Simple FPTAS for Counting Edge Covers. 341-348 - László Egri, Pavol Hell, Benoît Larose, Arash Rafiey:
Space complexity of list H-colouring: a dichotomy. 349-365 - Joël Ouaknine, James Worrell:
Positivity Problems for Low-Order Linear Recurrence Sequences. 366-379 - Daniel Bienstock, Alexander Michalka:
Polynomial Solvability of Variants of the Trust-Region Subproblem. 380-390 - Ishay Haviv, Oded Regev:
On the Lattice Isomorphism Problem. 391-404 - Greg Aloupis, John Iacono
The Complexity of Order Type Isomorphism. 405-415 - Dan Alistarh, James Aspnes, Michael A. Bender, Rati Gelashvili, Seth Gilbert
Dynamic Task Allocation in Asynchronous Shared Memory. 416-435 - Niv Buchbinder
Competitive Analysis via Regularization. 436-444 - Monik Khare, Claire Mathieu, Neal E. Young
First Come First Served for Online Slot Allocation and Huffman Coding. 445-454 - Anupam Gupta, Amit Kumar
Online Steiner Tree with Deletions. 455-467 - Anupam Gupta, Amit Kumar
Maintaining Assignments Online: Matching, Scheduling, and Flows. 468-479 - Piotr Indyk, Michael Kapralov
(Nearly) Sample-Optimal Sparse Fourier Transform. 480-499 - Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang:
Learning Sparse Polynomial Functions. 500-510 - Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi:
Learning Entangled Single-Sample Gaussians. 511-522 - Zhiyi Huang
Exploiting Metric Structure for Efficient Private Query Release. 523-534 - Noga Alon, Sagi Snir, Raphael Yuster:
On the compatibility of quartet trees. 535-545 - Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn:
A New Perspective on Vertex Connectivity. 546-561 - Yutaro Yamaguchi:
Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity. 562-569 - Daniel Lokshtanov, Martin Vatshelle, Yngve Villanger:
Independent Set in P5-Free Graphs in Polynomial Time. 570-581 - Fedor V. Fomin, Ioan Todinca
Large induced subgraphs via triangulations and CMSO. 582-583 - Andreas Björklund, Petteri Kaski, Lukasz Kowalik
Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time. 594-603 - René Sitters:
Polynomial time approximation schemes for the traveling repairman and other minimum latency problems. 604-616 - David Eisenstat, Philip N. Klein, Claire Mathieu:
Approximating k-center in planar graphs. 617-627 - Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. 628-644 - Anna Adamaszek
A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices. 645-656 - Lin Chen, Klaus Jansen, Guochuan Zhang
On the optimality of approximation schemes for the classical scheduling problem. 657-668 - Gregory T. Minton, Eric Price:
Improved Concentration Bounds for Count-Sketch. 669-686 - Amit Chakrabarti, Graham Cormode
Annotations for Sparse Data Streams. 687-706 - Mina Ghashami, Jeff M. Phillips:
Relative Errors for Deterministic Low-Rank Matrix Approximations. 707-717 - David P. Woodruff, Qin Zhang
An Optimal Lower Bound for Distinct Elements in the Message Passing Model. 718-733 - Michael Kapralov
Approximating matching size from random streams. 734-751 - Pierre-Etienne Meunier, Matthew J. Patitz
Intrinsic universality in tile self-assembly requires cooperation. 752-771 - David Doty:
Timing in chemical reaction networks. 772-784 - Valerie King, Jared Saia:
Faster Agreement via a Spectral Method for Detecting Malicious Behavior. 785-800 - George Giakkoupis:
Tight Bounds for Rumor Spreading with Vertex Expansion. 801-815 - Martin Dietzfelbinger
Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids. 816-829 - Michel X. Goemans, Thomas Rothvoß:
Polynomiality for Bin Packing with a Constant Number of Item Types. 830-839 - Alberto Del Pia
Integer quadratic programming in the plane. 840-846 - Thomas Dueholm Hansen, Haim Kaplan, Uri Zwick:
Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles. 847-860 - Georgios Piliouras, Jeff S. Shamma:
Optimization Despite Chaos: Convex Relaxations to Complex Limit Sets via Poincaré Recurrence. 861-873 - Thomas Dueholm Hansen, Mike Paterson, Uri Zwick:
Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. 874-881 - Michael Etscheid, Heiko Röglin
Smoothed Analysis of Local Search for the Maximum-Cut Problem. 882-889 - Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. 890-906 - David G. Harris, Aravind Srinivasan:
A constructive algorithm for the Lovász Local Lemma on permutations. 907-925 - Nicholas J. A. Harvey, Neil Olver:
Pipage Rounding, Pessimistic Estimators and Matrix Concentration. 926-945 - Christian Borgs
Maximizing Social Influence in Nearly Optimal Time. 946-957 - Michael A. Bender, Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, Samuel McCauley:
Cache-Adaptive Algorithms. 958-971 - Stephen Alstrup, Esben Bistrup Halvorsen, Kasper Green Larsen:
Near-optimal labeling schemes for nearest common ancestors. 972-982 - Peyman Afshani, Cheng Sheng, Yufei Tao
Concurrent Range Reporting in Two-Dimensional Space. 983-994 - Timothy M. Chan, J. Ian Munro, Venkatesh Raman:
Selection and Sorting in the "Restore" Model. 995-1004 - Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan:
Disjoint Set Union with Randomized Linking. 1005-1017 - Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn:
Beyond Locality-Sensitive Hashing. 1018-1028 - Lior Kamma, Robert Krauthgamer, Huy L. Nguyen:
Cutting corners cheaply, or how to remove Steiner points. 1029-1040 - Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck
Better Approximation Algorithms for the Graph Diameter. 1041-1052 - Monika Henzinger
A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths. 1053-1072 - Merav Parter, David Peleg:
Fault Tolerant Approximate BFS Structures. 1073-1092 - Sungjin Im, Benjamin Moseley:
New Approximations for Reordering Buffer Management. 1093-1111 - T.-H. Hubert Chan, Fei Chen, Xiaowei Wu
Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints. 1112-1122 - Nikhil R. Devanur, Zhiyi Huang:
Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms. 1123-1140 - Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein:
Hallucination Helps: Energy Efficient Virtual Circuit Routing. 1141-1153 - Will Ma:
Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract. 1154-1163 - Tereza Klimosová, Daniel Král':
Hereditary properties of permutations are strongly testable. 1164-1173 - Clément L. Canonne, Dana Ron, Rocco A. Servedio
Testing equivalence between distributions using conditional samples. 1174-1192 - Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant:
Optimal Algorithms for Testing Closeness of Discrete Distributions. 1193-1203 - Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, Chenggang Wu:
Testing Surface Area. 1204-1214 - Ben Cousins, Santosh S. Vempala:
A Cubic Algorithm for Computing Gaussian Volume. 1215-1228 - Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar:
Non-Uniform Graph Partitioning. 1229-1243 - Anand Louis, Konstantin Makarychev:
Approximation Algorithm for Sparsest k-Partitioning. 1244-1255 - Shayan Oveis Gharan, Luca Trevisan:
Partitioning into Expanders. 1256-1266 - Lorenzo Orecchia, Zeyuan Allen Zhu:
Flow-Based Algorithms for Local Graph Clustering. 1267-1286 - Isabelle Stanton:
Streaming Balanced Graph Partitioning Algorithms for Random Graphs. 1287-1301 - Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos
The Complexity of Optimal Mechanism Design. 1302-1318 - Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
The Complexity of Optimal Multidimensional Pricing. 1319-1328 - Jugal Garg, Vijay V. Vazirani:
On Computability of Equilibria in Markets with Production. 1329-1340 - Shaddin Dughmi, Nicole Immorlica, Aaron Roth
Constrained Signaling in Auction Design. 1341-1357 - Pablo Daniel Azar, Robert Kleinberg, S. Matthew Weinberg
Prophet Inequalities with Limited Information. 1358-1377 - Esther Ezra:
A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension. 1378-1388 - Peyman Afshani, Konstantinos Tsakalidis:
Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges. 1389-1398 - Kevin Buchin, Maike Buchin, Wouter Meulemans, Wolfgang Mulzer
Four Soviets Walk the Dog - with an Application to Alt's Conjecture. 1399-1413 - Peyman Afshani:
Fast Computation of Output-Sensitive Maxima in a Word RAM. 1414-1423 - Jean Cardinal, Kolja B. Knauer, Piotr Micek, Torsten Ueckerdt:
Making Octants Colorful and Related Covering Decomposition Problems. 1424-1432 - Niv Buchbinder
Submodular Maximization with Cardinality Constraints. 1433-1452 - Amol Deshpande, Lisa Hellerstein, Devorah Kletenik
Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover. 1453-1466 - Justin Ward, Stanislav Zivný:
Maximizing Bisubmodular and k-Submodular Functions. 1468-1481 - Sanjeev Khanna, Brendan Lucier:
Influence Maximization in Undirected Networks. 1482-1496 - Ashwinkumar Badanidiyuru, Jan Vondrák:
Fast algorithms for maximizing submodular functions. 1497-1514 - Jelani Nelson, Eric Price, Mary Wootters:
New constructions of RIP matrices with fast multiplication and fewer rows. 1515-1528 - Bubacarr Bah
Model-based Sketching and Recovery with Expanders. 1529-1543 - Chinmay Hegde, Piotr Indyk, Ludwig Schmidt:
Approximation-Tolerant Model-Based Compressive Sensing. 1544-1561 - Yi Li, Huy L. Nguyen, David P. Woodruff:
On Sketching Matrix Norms and the Top Singular Vector. 1562-1581 - Andrea Farruggia, Paolo Ferragina, Antonio Frangioni
Bicriteria data compression. 1582-1595 - Stefan Kratsch, Geevarghese Philip, Saurabh Ray:
Point Line Cover: The Easy Kernel is Essentially Tight. 1596-1606 - Subhash Khot, Rishi Saket:
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs. 1607-1625 - Bundit Laekhanukit
Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems. 1626-1643 - Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou:
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. 1644-1658 - Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou
Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs. 1659-1677 - Attila Bernáth, Yusuke Kobayashi:
The Generalized Terminal Backup Problem. 1678-1686 - Mohit Singh, László A. Végh
Approximating Minimum Cost Connectivity Orientation and Augmentation. 1687-1701 - Samir Khuller, Manish Purohit, Kanthi K. Sarpatwar:
Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems. 1702-1713 - Wang Chi Cheung, Michel X. Goemans, Sam Chiu-wai Wong:
Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs. 1714-1726 - Anupam Gupta, Anastasios Sidiropoulos:
Minimum d-dimensional arrangement with fixed points. 1727-1738 - M. S. Ramanujan, Saket Saurabh:
Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts. 1739-1748 - Yoichi Iwata, Keigo Oka, Yuichi Yoshida:
Linear-Time FPT Algorithms via Network Flow. 1749-1761 - Magnus Wahlström
Half-integrality, LP-branching and FPT Algorithms. 1762-1781 - Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx:
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). 1782-1801 - Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh:
A Near-Optimal Planarization Algorithm. 1802-1811 - Philip N. Klein, Dániel Marx:
A subexponential parameterized algorithm for Subset TSP on planar graphs. 1812-1830 - Noga Alon, Mohsen Ghaffari, Bernhard Haeupler
Broadcast Throughput in Radio Networks: Routing vs. Network Coding. 1831-1843 - Raef Bassily, Adam D. Smith:
Causal Erasure Channels. 1844-1857 - Venkatesan Guruswami, Chaoping Xing:
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. 1858-1866 - Ryan Williams
Finding orthogonal vectors in discrete structures. 1867-1877 - Shengyu Zhang:
Efficient quantum protocols for XOR functions. 1878-1885
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-14 20:47 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: