ACM Transactions on Algorithms

In this article, we study the computational complexity of solving a class of block structured integer programs (IPs), the so-called multistage stochastic IPs. A multistage stochastic IP is an IP of the form min {c^Tx | Ax = b, x ≥ 0, x integral} where the ...

The greedy spanner in a low-dimensional Euclidean space is a fundamental geometric construction that has been extensively studied over three decades, as it possesses the two most basic properties of a good spanner: constant maximum degree and constant ...

We revisit Hopcroft’s problem and related fundamental problems about geometric range searching. Given n points and n lines in the plane, we show how to count the number of point-line incidence pairs or the number of point-above-line pairs in O(n^4/3) time, ...

We give an isomorphism test that runs in time n^polylog(h) on all n-vertex graphs excluding some h-vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time n^polylog(h) (Babai, STOC 2016) and n^{f(...

A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses S is the smallest number of edit operations (insertions, deletions, and substitutions) needed ...

Given a large set U where each item a∈ U has weight w(a), we want to estimate the total weight \(W=\sum _{a∈ U} w(a)\) to within factor of 1± ɛ with some constant probability > 1/2. Since n=|U| is large, we want to do this without looking at the ...