Search ACM DL

Search Issue

enter search term and/or author name

**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 ⩽ *r* ⩽ *k*. 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 C*O*(*c ^{n}*) (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 *r*_{1}, *r*_{2}, …, *r _{k}* 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...