Abstract. We describe algorithms to efficiently compute minimum [Formula: see text]-cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph [Formula: see text] with [Formula: see text] vertices embedded on an orientable surface of genus [Formula: see text], our algorithms can solve either problem in [Formula: see text] or [Formula: see text] time, whichever is better. When [Formula: see text] is a constant, our [Formula: see text] time algorithms match the best running times known for computing minimum cuts in planar graphs. Our algorithms for minimum cuts rely on reductions to the problem of finding a minimum-weight subgraph in a given [Formula: see text]-homology class, and we give efficient algorithms for this latter problem as well. If [Formula: see text] is embedded on a surface with genus [Formula: see text] and [Formula: see text] boundary components, these algorithms run in [Formula: see text] and [Formula: see text] time. We also prove that finding a minimum-weight subgraph homologous to a single input cycle is NP-hard, showing that it is likely impossible to improve upon the exponential dependencies on [Formula: see text] for this latter problem.

On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: We give an algorithm that runs in \(\widetilde{O}(mn^{2k-2})\) time for finding a minimum k -cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimum k -cut problem, for k > 2. We give an algorithm that runs in \(\widetilde{O}(n^{\max \lbrace r,2k-2\rbrace })\) time for finding a minimum k -cut in hypergraphs of constant rank r . This algorithm betters the previous best running times for both the minimum cut and minimum k -cut problems for dense hypergraphs. Both of our algorithms are Monte Carlo, i.e., they return a minimum k -cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a generic branching randomized contraction technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge- k -cut on hedgegraphs, which generalize hypergraphs.

We describe the first strongly subquadratic time algorithm with subexponential approximation ratio for approximately computing the Fréchet distance between two polygonal chains. Specifically, let $P$ and $Q$ be two polygonal chains with $n$ vertices in $d$-dimensional Euclidean space, and let $α\in [\sqrt{n}, n]$. Our algorithm deterministically finds an $O(α)$-approximate Fréchet correspondence in time $O((n^3 / α^2) \log n)$. In particular, we get an $O(n)$-approximation in near-linear $O(n \log n)$ time, a vast improvement over the previously best know result, a linear time $2^{O(n)}$-approximation. As part of our algorithm, we also describe how to turn any approximate decision procedure for the Fréchet distance into an approximate optimization algorithm whose approximation ratio is the same up to arbitrarily small constant factors. The transformation into an approximate optimization algorithm increases the running time of the decision procedure by only an $O(\log n)$ factor.

We give an $O(k^3 n \log n \min(k,\log^2 n) \log^2(nC))$-time algorithm for computing maximum integer flows in planar graphs with integer arc {\em and vertex} capacities bounded by $C$, and $k$ sources and sinks. This improves by a factor of $\max(k^2,k\log^2 n)$ over the fastest algorithm previously known for this problem [Wang, SODA 2019]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses $O(k)$ invocations of an $O(k^3 n \log^3 n)$-time algorithm for maximum flow algorithm in a planar graph with $k$ apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we show two alternatives for computing flows in the $k$-apex graphs that arise in our modification of Wang's procedure faster than the algorithm of Borradaile et al. In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance push-relabel algorithm of Goldberg and Tarjan~[JACM 1988].

The geometric transportation problem takes as input a set of points $P$ in $d$-dimensional Euclidean space and a supply function $μ: P \to \mathbb{R}$. The goal is to find a transportation map, a non-negative assignment $τ: P \times P \to \mathbb{R}_{\geq 0}$ to pairs of points, so the total assignment leaving each point is equal to its supply, i.e., $\sum_{r \in P} τ(q, r) - \sum_{p \in P} τ(p, q) = μ(q)$ for all points $q \in P$. The goal is to minimize the weighted sum of Euclidean distances for the pairs, $\sum_{(p, q) \in P \times P} τ(p, q) \cdot ||q - p||_2$. We describe the first algorithm for this problem that returns, with high probability, a $(1 + \varepsilon)$-approximation to the optimal transportation map in $n\varepsilon^{-O(d)}\log^{O(d)}{n}$ time. In contrast to the previous best algorithms for this problem, our near-linear running time bound is independent of the spread of $P$ and the magnitude of its real-valued supplies.

Edit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space. Therefore, the geometric edit distance (GED) has been studied. In this paper, we describe the first strictly sublinear approximate near-linear time algorithm for computing the GED of two point sequences in constant dimensional Euclidean space. Specifically, we present a randomized (O(n\log^2n)) time (O(\sqrt n))-approximation algorithm. Then, we generalize our result to give a randomized $α$-approximation algorithm for any $α\in [\sqrt{\log n}, \sqrt{n / \log n}]$, running in time $O(n^2/α^2 \log n)$. Both algorithms are Monte Carlo and return approximately optimal solutions with high probability.

On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: We give an algorithm that runs in Õ(mn2k–2) time for finding a minimum k-cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimum k-cut problem, for k > 2. We give an algorithm that runs in Õ(nmax{r, 2k–2}) time for finding a minimum k-cut in hypergraphs of constant rank r. This algorithm betters the previous best running times for both the minimum cut and minimum k-cut problems for dense hypergraphs. Both of our algorithms are Monte Carlo, i.e., they return a minimum k-cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a generic branching randomized contraction technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-k-cut on hedgegraphs, which generalize hypergraphs.

We propose a model for subtrajectory clustering ---the clustering of subsequences of trajectories; each cluster of subtrajectories is represented as a pathlet, a sequence of points that is not necessarily a subsequence of an input trajectory. Given a set of trajectories, our clustering model attempts to capture the shared portions between them by assuming each trajectory is a concatenation of a small set of pathlets, with possible gaps in between. We present a single objective function for finding the optimal collection of pathlets that best represents the trajectories taking into account noise and other artifacts of the data. We show that the subtrajectory clustering problem is NP-Hard and present fast approximation algorithms for subtrajectory clustering. We further improve the running time of our algorithm if the input trajectories are "well-behaved." Finally, we present experimental results on both real and synthetic data sets. We show via visualization and quantitative analysis that the algorithm indeed handles the desiderata of being robust to variations, being efficient and accurate, and being data-driven.

Let G be an edge-weighted directed graph with n vertices embedded on an orientable surface of genus g. We describe a simple deterministic lexicographic perturbation scheme that guarantees uniqueness of minimum-cost flows and shortest paths in G. The perturbations take O(gn) time to compute. We use our perturbation scheme in a black box manner to derive a deterministic O(n loglogn) time algorithm for minimum cut in directed edge-weighted planar graphs and a deterministic O(g2 n logn) time proprocessing scheme for the multiple-source shortest paths problem of computing a shortest path oracle for all vertices lying on a common face of a surface embedded graph. The latter result yields faster deterministic near-linear time algorithms for a variety of problems in constant genus surface embedded graphs.

The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the GH distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time O (min n , √ rn )-approximation algorithm for computing the GH distance between a pair of metric trees, where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an O (√ n )-approximation algorithm 1 .

We study a path-planning problem amid a set O of obstacles in R 2 , in which we wish to compute a short path between two points while also maintaining a high clearance from O; the clearance of a point is its distance from a nearest obstacle in O. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ε ∈ (0, 1]. Our algorithm computes in time O ( n 2 /ε 2 log n /ε) a path of total cost at most (1 + ε) times the cost of the optimal path.

Let R, B be a set of n points in R^d, for constant d, where the points of R have integer supplies, points of B have integer demands, and the sum of supply is equal to the sum of demand. Let d(.,.) be a suitable distance function such as the L_p distance. The transportation problem asks to find a map tau : R x B --> N such that sum_{b in B}tau(r,b) = supply(r), sum_{r in R}tau(r,b) = demand(b), and sum_{r in R, b in B} tau(r,b) d(r,b) is minimized. We present three new results for the transportation problem when d(.,.) is any L_p metric: * For any constant epsilon > 0, an O(n^{1+epsilon}) expected time randomized algorithm that returns a transportation map with expected cost O(log^2(1/epsilon)) times the optimal cost. * For any epsilon > 0, a (1+epsilon)-approximation in O(n^{3/2}epsilon^{-d}polylog(U)polylog(n)) time, where U is the maximum supply or demand of any point. * An exact strongly polynomial O(n^2 polylog n) time algorithm, for d = 2.

Let M be a triangulated, orientable 2-manifold of genus g without boundary, and let h be a height function over M that is linear within each triangle. We present a kinetic data structure (KDS) for maintaining the Reeb graph R of h as the heights of M's vertices vary continuously with time. Assuming the heights of two vertices of M become equal only O(1) times, the KDS processes O((k + g) n \polylog n) events; n is the number of vertices in M, and k is the number of external events which change the combinatorial structure of R. Each event is processed in O(\log^2 n) time, and the total size of our KDS is O(gn). The KDS can be extended to maintain an augmented Reeb graph as well.

We present the first subquadratic algorithms for computing similarity between a pair of point sequences in R^d, for any fixed d > 1, using dynamic time warping (DTW) and edit distance, assuming that the point sequences are drawn from certain natural families of curves. In particular, our algorithms compute (1 + eps)-approximations of DTW and ED in near-linear time for point sequences drawn from k-packed or k-bounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is k-packed if the length of its intersection with any ball of radius r is at most kr, and it is k-bounded if the sub-curve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for d = 1. The commonly used dynamic programming algorithms for these distance measures reduce the problem to computing a minimum-weight path in a grid graph. Our algorithms work by constructing a small set of rectangular regions that cover the grid vertices. The weights of vertices inside each rectangle are roughly the same, and we develop efficient procedures to compute the approximate minimum-weight paths through these rectangles.

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n.

We propose parallel algorithms in the massively parallel communication (MPC) model (e.g. MapReduce) for processing large terrain elevation data (represented as a 3D point cloud) that are too big to fit on one machine. In particular, given a set S of 3D points that is distributed across multiple machines, we present a simple randomized algorithm to construct a TIN DEM of S by computing the Delaunay triangulation of the xy-projections of points in S, which is also stored across multiple machines. With high probability, the algorithm works in O(1) rounds and the total work performed is O(n log n). Next, we describe an efficient algorithm in the MPC model for computing the contour tree of the resulting DEM. Under some assumptions on the input, the algorithm works in O(1) rounds and the total work performed is O(n log n).

Dynamic time warping (DTW) is a widely used curve similarity measure. We present a simple and efficient (1 + ε)- approximation algorithm for DTW between a pair of point sequences, say, P and Q, each of which is sampled from a curve. We prove that the running time of the algorithm is O([EQUATION]n log σ) for a pair of k-packed curves with a total of n points, assuming that the spreads of P and Q are bounded by σ. The spread of a point set is the ratio of the maximum to the minimum pairwise distance, and a curve is called K- packed if the length of its intersection with any disk of radius r is at most Kr. Although an algorithm with similar asymptotic time complexity was presented in [1], our algorithm is considerably simpler and more efficient in practice.

With the massive amounts of data available today, it is common to store and process data using multiple machines. Parallel programming platforms such as MapReduce and its variants are popular frameworks for handling such large data. We present the first provably efficient algorithms to compute, store, and query data structures for range queries and approximate nearest neighbor queries in a popular parallel computing abstraction that captures the salient features of MapReduce and other massively parallel communication (MPC) models. In particular, we describe algorithms for $kd$-trees, range trees, and BBD-trees that only require O(1) rounds of communication for both preprocessing and querying while staying competitive in terms of running time and workload to their classical counterparts. Our algorithms are randomized, but they can be made deterministic at some increase in their running time and workload while keeping the number of rounds of communication to be constant.

We study a path-planning problem amid a set ℴ of obstacles in ℝ2, in which we wish to compute a short path between two points while also maintaining a high clearance from ℴ; the clearance of a point is its distance from a nearest obstacle in ℴ. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let n be the total number of obstacle vertices and let ∊ ∊ (0, 1]. Our algorithm computes in time a path of total cost at most (1 + ∊) times the cost of the optimal path.

Given an undirected graph with edge costs and node weights, the minimum bisection problem asks for a partition of the nodes into two parts of equal weight such that the sum of edge costs between the parts is minimized. We give a polynomial time bicriteria approximation scheme for bisection on planar graphs. Specifically, let W be the total weight of all nodes in a planar graph G. For any constant ε > 0, our algorithm outputs a bipartition of the nodes such that each part weighs at most W/2 + ε and the total cost of edges crossing the partition is at most (1+ε) times the total cost of the optimal bisection. The previously best known approximation for planar minimum bisection, even with unit node weights, was ~O(log n). Our algorithm actually solves a more general problem where the input may include a target weight for the smaller side of the bipartition.

Let $G$ be a directed graph with n vertices embedded on an orientable surface of genus g with two designated vertices s and t. We show that counting the minimum (s,t)-cuts in G is fixed parameter tractable in g. Specially, we give a 2O(g) n2 time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are few prior results that are fixed parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample a minimum cut uniformly at random in O(gn) time per sample.

Let G be a graph embedded on a surface of genus g with b boundary cycles. We describe algorithms to compute multiple types of non-trivial cycles in G, using different techniques depending on whether or not G is an undirected graph. If G is undirected, then we give an algorithm to compute a shortest non-separating cycle in G in 2O(g) n log log n time. Similar algorithms are given to compute a shortest non-contractible or non-null-homologous cycle in 2O(g+b) n log log n time. Our algorithms for undirected G combine an algorithm of Kutz with known techniques for efficiently enumerating homotopy classes of curves that may be shortest non-trivial cycles. Our main technical contributions in this work arise from assuming G is a directed graph with possibly asymmetric edge weights. For this case, we give an algorithm to compute a shortest non-contractible cycle in G in O((g3 + gb) n log n) time. In order to achieve this time bound, we use a restriction of the infinite cyclic cover that may be useful in other contexts. We also describe an algorithm to compute a shortest non-null-homologous cycle in G in O((g2 + gb)n log n) time, extending a known algorithm of Erickson to compute a shortest non-separating cycle. In both the undirected and directed cases, our algorithms improve the best time bounds known for many values of g and b.

In this paper, we consider scheduling parallelizable jobs in the non-clairvoyant speed scaling setting to minimize the objective of weighted flow time plus energy. Previously, strong lower bounds were shown on this model in the unweighted setting even when the algorithm is given a constant amount of resource augmentation over the optimal solution. However, these lower bounds were given only for certain families of algorithms that do not recognize the parallelizability of alive jobs. In this work, we circumvent previous lower bounds shown and give a scalable algorithm under the natural assumption that the algorithm can know the current parallelizability of a job. When a general power function is considered, this is also the first algorithm that has a constant competitive ratio for the problem using any amount of resource augmentation.

It is well-known that SRPT is optimal for minimizing flow time on machines that run one job at a time. However, running one job at a time is a big under-utilization for modern systems where sharing, simultaneous execution, and virtualization-enabled consolidation are a common trend to boost utilization. Such machines, used in modern large data centers and clouds, are powerful enough to run multiple jobs/VMs at a time subject to overall CPU, memory, network, and disk capacity constraints. Motivated by this prominent trend and need, in this work, we give the first scheduling algorithms to minimize weighted flow time on such capacitated machines. To capture the difficulty of the problem, we show that without resource augmentation, no online algorithm can achieve a bounded competitive ratio. We then investigate algorithms with a small resource augmentation in speed and/or capacity. Our first result is a simple (2 + ε)-capacity O(1/ε)-competitive greedy algorithm. Using only speed augmentation, we then obtain a 1.75-speed O(1)-competitive algorithm. Our main technical result is a near-optimal (1 + ε)-speed, (1+ε)-capacity O(1/ε3)-competitive algorithm using a novel combination of knapsacks, densities, job classification into categories, and potential function methods. We show that our results also extend to the multiple unrelated capacitated machines setting.

We give a deterministic algorithm to find the minimum cut in a surface-embedded graph in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, our algorithm computes the minimum cut in gO(g)n log log n time, matching the running time of the fastest algorithm known for planar graphs, due to Łącki and Sankowski, for any constant g. Indeed, our algorithm calls Łącki and Sankowski's recent O(n log log n) time planar algorithm as a subroutine. Previously, the best time bounds known for this problem followed from two algorithms for general sparse graphs: a randomized algorithm of Karger that runs in O(n log3 n) time and succeeds with high probability, and a deterministic algorithm of Nagamochi and Ibaraki that runs in O(n2 log n) time. We can also achieve a deterministic gO(g)n2 log log n time bound by repeatedly applying the best known algorithm for minimum (s, t)-cuts in surface graphs. The bulk of our work focuses on the case where the dual of the minimum cut splits the underlying surface into multiple components with positive genus.

Due to its optimality on a single machine for the problem of minimizing average flow time, Shortest-Remaining-Processing-Time (\srpt) appears to be the most natural algorithm to consider for the problem of minimizing average flow time on multiple identical machines. It is known that $\srpt$ achieves the best possible competitive ratio on multiple machines up to a constant factor. Using resource augmentation, $\srpt$ is known to achieve total flow time at most that of the optimal solution when given machines of speed $2- \frac{1}{m}$. Further, it is known that $\srpt$'s competitive ratio improves as the speed increases; $\srpt$ is $s$-speed $\frac{1}{s}$-competitive when $s \geq 2- \frac{1}{m}$. However, a gap has persisted in our understanding of $\srpt$. Before this work, the performance of $\srpt$ was not known when $\srpt$ is given $(1+\eps)$-speed when $0 < \eps < 1-\frac{1}{m}$, even though it has been thought that $\srpt$ is $(1+\eps)$-speed $O(1)$-competitive for over a decade. Resolving this question was suggested in Open Problem 2.9 from the survey "Online Scheduling" by Pruhs, Sgall, and Torng \cite{PruhsST}, and we answer the question in this paper. We show that $\srpt$ is \emph{scalable} on $m$ identical machines. That is, we show $\srpt$ is $(1+\eps)$-speed $O(\frac{1}{\eps})$-competitive for $\eps >0$. We complement this by showing that $\srpt$ is $(1+\eps)$-speed $O(\frac{1}{\eps^2})$-competitive for the objective of minimizing the $\ell_k$-norms of flow time on $m$ identical machines. Both of our results rely on new potential functions that capture the structure of \srpt. Our results, combined with previous work, show that $\srpt$ is the best possible online algorithm in essentially every aspect when migration is permissible.