Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 12 Issue 4, September 2016

Adaptive and Approximate Orthogonal Range Counting
Timothy M. Chan, Bryan T. Wilkinson
Article No.: 45
DOI: 10.1145/2830567

We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting. All the results are in the w-bit word RAM model.

—It is well known that there are linear-space...

Agnostic Learning in Permutation-Invariant Domains
Karl Wimmer
Article No.: 46
DOI: 10.1145/2963169

We generalize algorithms from computational learning theory that are successful under the uniform distribution on the Boolean hypercube {0, 1}n to algorithms successful on permutation-invariant distributions,...

Maximizing k-Submodular Functions and Beyond
Justin Ward, Stanislav Živný
Article No.: 47
DOI: 10.1145/2850419

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k ⩾ 2 and 1 ⩽ rk. We give an...

Tight Lower Bound for the Channel Assignment Problem
Arkadiusz Socała
Article No.: 48
DOI: 10.1145/2876505

We study the complexity of the Channel Assignment problem. An open problem asks whether Channel Assignment admits an O(cn) (times a polynomial in the bit size) time algorithm,...

Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
Chaitanya Swamy
Article No.: 49
DOI: 10.1145/2963170

We consider the matroid median problem [Krishnaswamy et al. 2011], wherein we are given a set of facilities with opening costs and a matroid on the facility-set, and clients with demands and connection costs, and we seek to open an...

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
Michael Elkin, Seth Pettie
Article No.: 50
DOI: 10.1145/2888397

Thorup and Zwick [2001a] proposed a landmark distance oracle with the following properties. Given an n-vertex undirected graph G = (V, E) and a parameter k = 1, 2, …, their oracle has size...

Space-Constrained Interval Selection
Yuval Emek, Magnús M. Halldórsson, Adi Rosén
Article No.: 51
DOI: 10.1145/2886102

We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic 2-approximation streaming algorithm for this problem is developed, together with an algorithm...

Compressed Cache-Oblivious String B-Tree
Paolo Ferragina, Rossano Venturini
Article No.: 52
DOI: 10.1145/2903141

In this article, we study three variants of the well-known prefix-search problem for strings, and we design solutions for the cache-oblivious model which improve the best known results. Among these contributions, we close (asymptotically) the...

Data Structures for Path Queries
Meng He, J. Ian Munro, Gelin Zhou
Article No.: 53
DOI: 10.1145/2905368

Consider a tree T on n nodes, each having a weight drawn from [1‥σ]. In this article, we study the problem of supporting various path queries over the tree T. The path counting query asks for the number of the nodes...

Approximation Algorithms for Movement Repairmen
Mohammad Taghi Hajiaghayi, Rohit Khandekar, Mohammad Reza Khani, Guy Kortsarz
Article No.: 54
DOI: 10.1145/2908737

In the Movement Repairmen (MR) problem, we are given a metric space (V, d) along with a set R of k repairmen r1, r2, …, rk with their start depots...

On Hierarchical Routing in Doubling Metrics
T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou
Article No.: 55
DOI: 10.1145/2915183

We study the problem of routing in doubling metrics and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with a small amount of routing information stored at each vertex). We say that a...

Addendum to “Dominator Tree Certification and Divergent Spanning Trees”
Loukas Georgiadis, Robert E. Tarjan
Article No.: 56
DOI: 10.1145/2928271

Deletion Without Rebalancing in Binary Search Trees
Siddhartha Sen, Robert E. Tarjan, David Hong Kyun Kim
Article No.: 57
DOI: 10.1145/2903142

We address the vexing issue of deletions in balanced trees. Rebalancing after a deletion is generally more complicated than rebalancing after an insertion. Textbooks neglect deletion rebalancing, and many B-tree--based database systems do not do...