![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
ACM Transactions on Algorithms, Volume 12
Volume 12, Number 1, February 2016
- Yuval Rabani
, Andréa W. Richa, Jared Saia, David P. Woodruff:
Editorial to the Special Issue on SODA'12. 1:1 - Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou:
Approximation Algorithms and Hardness of the k-Route Cut Problem. 2:1-2:40 - Guillaume Moroz, Boris Aronov
:
Computing the Distance between Piecewise-Linear Bivariate Functions. 3:1-3:13 - Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
, Jesper Nederlof, Pekka Parviainen:
Fast Zeta Transforms for Lattices with Few Irreducibles. 4:1-4:19 - Alexandr Andoni, Huy L. Nguyên:
Width of Points in the Streaming Model. 5:1-5:10 - Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu:
Bypassing UGC from Some Optimal Geometric Inapproximability Results. 6:1-6:25
- Ofer Neiman, Shay Solomon:
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching. 7:1-7:15 - Mihai Patrascu, Mikkel Thorup
:
On the k-Independence Required by Linear Probing and Minwise Independence. 8:1-8:27 - Marcel Kenji de Carli Silva, Nicholas J. A. Harvey, Cristiane M. Sato
:
Sparse Sums of Positive Semidefinite Matrices. 9:1-9:17 - Anupam Gupta, Viswanath Nagarajan, R. Ravi:
Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets. 10:1-10:21 - Loukas Georgiadis
, Robert E. Tarjan:
Dominator Tree Certification and Divergent Spanning Trees. 11:1-11:42 - Oren Weimann
, Raphael Yuster:
Approximating the Diameter of Planar Graphs in Near Linear Time. 12:1-12:13
Volume 12, Number 2, February 2016
- Lukás Polácek, Ola Svensson:
Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation. 13:1-13:13 - Michael A. Bender, Jeremy T. Fineman, Seth Gilbert
, Robert E. Tarjan:
A New Approach to Incremental Cycle Detection and Related Problems. 14:1-14:22 - Ronald L. Graham, Linus Hamilton, Ariel Levavi, Po-Shen Loh
:
Anarchy Is Free in Network Creation. 15:1-15:10 - Thomas Bläsius, Ignaz Rutter
:
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems. 16:1-16:46 - Ioannis Koutis, Alex Levin, Richard Peng:
Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices. 17:1-17:16 - Martin Aumüller, Martin Dietzfelbinger
:
Optimal Partitioning for Dual-Pivot Quicksort. 18:1-18:36 - Miklós Ajtai, Vitaly Feldman
, Avinatan Hassidim, Jelani Nelson:
Sorting and Selection with Imprecise Comparisons. 19:1-19:19 - Alon Efrat
, Sándor P. Fekete, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela
:
Improved Approximation Algorithms for Relay Placement. 20:1-20:28 - Eun Jung Kim, Alexander Langer, Christophe Paul
, Felix Reidl
, Peter Rossmanith, Ignasi Sau
, Somnath Sikdar:
Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions. 21:1-21:41 - Ittai Abraham, Shiri Chechik, Cyril Gavoille, David Peleg:
Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension. 22:1-22:17 - Guy Kortsarz, Zeev Nutov:
A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2. 23:1-23:20 - Harold N. Gabow:
The Minset-Poset Approach to Representations of Graph Connectivity. 24:1-24:73 - Michael Dinitz
, Guy Kortsarz, Ran Raz
:
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner. 25:1-25:16 - Boris Aronov
, Anne Driemel
, Marc J. van Kreveld
, Maarten Löffler, Frank Staals:
Segmentation of Trajectories on Nonmonotone Criteria. 26:1-26:28
Volume 12, Number 3, June 2016
- Goran Konjevod
, Andréa W. Richa, Donglin Xia:
Scale-Free Compact Routing Schemes in Networks of Low Doubling Dimension. 27:1-27:29 - V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan:
Distributed Algorithms for End-to-End Packet Scheduling in Wireless Ad Hoc Networks. 28:1-28:25 - Michael Elkin, Shay Solomon:
Fast Constructions of Lightweight Spanners for General Graphs. 29:1-29:21 - Glencora Borradaile, Philip N. Klein:
The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs. 30:1-30:29 - Ioannis Koutis, Ryan Williams
:
LIMITS and Applications of Group Algebras for Parameterized Problems. 31:1-31:18 - Christian Konrad, Adi Rosén:
Approximating Semi-matchings in Streaming and in Two-Party Communication. 32:1-32:21 - Thomas Bläsius
, Ignaz Rutter
, Dorothea Wagner:
Optimal Orthogonal Graph Drawing with Convex Bend Costs. 33:1-33:32 - Lisa Fleischer, Rahul Garg, Sanjiv Kapoor, Rohit Khandekar, Amin Saberi:
A Simple and Efficient Algorithm for Computing Market Equilibria. 34:1-34:15 - Alexander Golovnev, Alexander S. Kulikov
, Ivan Mihajlin:
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. 35:1-35:17 - Mohammad Taghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha:
A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median. 36:1-36:19 - Anne Driemel
, Sariel Har-Peled
, Benjamin Raichel:
On the Expected Complexity of Voronoi Diagrams on Terrains. 37:1-37:20 - Ron Adany, Moran Feldman
, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai, Tami Tamir:
All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns. 38:1-38:25 - Philip Bille
, Johannes Fischer, Inge Li Gørtz
, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj:
Sparse Text Indexing in Small Space. 39:1-39:19 - Stefan Kratsch, Geevarghese Philip, Saurabh Ray:
Point Line Cover: The Easy Kernel is Essentially Tight. 40:1-40:16 - Marek Cygan
, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto
, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
:
On Problems as Hard as CNF-SAT. 41:1-41:24 - Amol Deshpande, Lisa Hellerstein, Devorah Kletenik
:
Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack. 42:1-42:28 - Adrian Dumitrescu, Csaba D. Tóth:
The Traveling Salesman Problem for Lines, Balls, and Planes. 43:1-43:29 - Siu-Wing Cheng
, Liam Mencel, Antoine Vigneron
:
A Faster Algorithm for Computing Straight Skeletons. 44:1-44:21
Volume 12, Number 4, September 2016
- Timothy M. Chan, Bryan T. Wilkinson:
Adaptive and Approximate Orthogonal Range Counting. 45:1-45:15 - Karl Wimmer:
Agnostic Learning in Permutation-Invariant Domains. 46:1-46:22 - Justin Ward, Stanislav Zivný:
Maximizing k-Submodular Functions and Beyond. 47:1-47:26 - Arkadiusz Socala:
Tight Lower Bound for the Channel Assignment Problem. 48:1-48:19 - Chaitanya Swamy:
Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications. 49:1-49:22 - Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. 50:1-50:31 - Yuval Emek, Magnús M. Halldórsson
, Adi Rosén:
Space-Constrained Interval Selection. 51:1-51:32 - Paolo Ferragina
, Rossano Venturini:
Compressed Cache-Oblivious String B-Tree. 52:1-52:17 - Meng He
, J. Ian Munro, Gelin Zhou:
Data Structures for Path Queries. 53:1-53:32 - Mohammad Taghi Hajiaghayi, Rohit Khandekar, Mohammad Reza Khani, Guy Kortsarz:
Approximation Algorithms for Movement Repairmen. 54:1-54:38 - T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou:
On Hierarchical Routing in Doubling Metrics. 55:1-55:22 - Loukas Georgiadis, Robert E. Tarjan:
Addendum to "Dominator Tree Certification and Divergent Spanning Trees". 56:1-56:3 - Siddhartha Sen, Robert E. Tarjan, David Hong Kyun Kim:
Deletion Without Rebalancing in Binary Search Trees. 57:1-57:31
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
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.