More Like this

1. Algorithms for Halfplane Coverage and Related Problems

   https://doi.org/10.4230/LIPIcs.SoCG.2024.79  

   Wang, Haitao; Xue, Jie (June 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an O(n^{4/3}log^{5/3}nlog^{O(1)}log n)-time algorithm for the problem, where n is the total number of all points and halfplanes. This improves the previously best algorithm of n^{10/3}2^{O(log^*n)} time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in O(nlog n) time, which improves the previously best algorithm of n^{4/3}2^{O(log^*n)} time and matches an Ω(nlog n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O(nlog n) time, which in turn leads to an O(nlog n)-time algorithm for computing an instance-optimal ε-kernel of a set of n points in the plane. Agarwal and Har-Peled presented an O(nklog n)-time algorithm for this problem in SoCG 2023, where k is the size of the ε-kernel; they also raised an open question whether the problem can be solved in O(nlog n) time. Our result thus answers the open question affirmatively. 

   more » « less
2. A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings

   Lahn, Nathaniel; Raghvendra, Sharath (June 2019, Leibniz international proceedings in informatics)

   We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph G(A cup B,E) with edge weights of 0 or 1. Let w <= n be an upper bound on the weight of any matching in G. Consider the subgraph induced by all the edges of G with a weight 0. Suppose every connected component in this subgraph has O(r) vertices and O(mr/n) edges. We present an algorithm to compute a maximum cardinality matching in G in O~(m(sqrt{w} + sqrt{r} + wr/n)) time. When all the edge weights are 1 (symmetrically when all weights are 0), our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm, which runs in O(m sqrt{n}) time. However, if we can carefully assign weights of 0 and 1 on its edges such that both w and r are sub-linear in n and wr=O(n^{gamma}) for gamma < 3/2, then we can compute maximum cardinality matching in G in o(m sqrt{n}) time. Using our algorithm, we obtain a new O~(n^{4/3}/epsilon^4) time algorithm to compute an epsilon-approximate bottleneck matching of A,B subsetR^2 and an 1/(epsilon^{O(d)}}n^{1+(d-1)/(2d-1)}) poly log n time algorithm for computing epsilon-approximate bottleneck matching in d-dimensions. All previous algorithms take Omega(n^{3/2}) time. Given any graph G(A cup B,E) that has an easily computable balanced vertex separator for every subgraph G'(V',E') of size |V'|^{delta}, for delta in [1/2,1), we can apply our algorithm to compute a maximum matching in O~(mn^{delta/1+delta}) time improving upon the O(m sqrt{n}) time taken by the HK-Algorithm. 

   more » « less
3. Multi-way Time Series Join on Multi-length Patterns

   https://doi.org/10.1109/ICDM51629.2021.00054  

   Mollah, Md Parvez; Souza, Vinicius M.; Mueen, Abdullah (December 2021, 2021 IEEE International Conference on Data Mining (ICDM))

   This paper introduces a new pattern mining task that considers aligning or joining a set of time series based on an arbitrary number of subsequences (i.e., patterns) with arbitrary lengths. Joining multiple time series along common patterns can be pivotal in clustering and summarizing large time series datasets. An exact algorithm to join hundreds of time series based on multi-length patterns is impractical due to the high computational costs. This paper proposes a fast algorithm named MultiPAL to join multiple time series at interactive speed to summarize large time series datasets. The algorithm exploits Matrix Profiles of the individual time series to enable a greedy search over possible joins. The algorithm is orders of magnitude faster than the exact solution and can utilize hundreds of Matrix Profiles. We evaluate our algorithm for sequential mining on data from various real-world domains, including power management and bioacoustics monitoring. 

   more » « less
4. An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint

   https://doi.org/10.1287/moor.2021.1224  

   Alaluf, Naor; Ene, Alina; Feldman, Moran; Nguyen, Huy L.; Suh, Andrew (February 2022, Mathematics of operations research)

   We study the problem of maximizing a non-monotone submodular function subject to a cardinality constraint in the streaming model. Our main contribution is a single-pass (semi-)streaming algorithm that uses roughly $$O(k / \varepsilon^2)$$ memory, where $$k$$ is the size constraint. At the end of the stream, our algorithm post-processes its data structure using any offline algorithm for submodular maximization, and obtains a solution whose approximation guarantee is $$\frac{\alpha}{1+\alpha}-\varepsilon$$, where $$\alpha$$ is the approximation of the offline algorithm. If we use an exact (exponential time) post-processing algorithm, this leads to $$\frac{1}{2}-\varepsilon$$ approximation (which is nearly optimal). If we post-process with the algorithm of \cite{buchbinder2019constrained}, that achieves the state-of-the-art offline approximation guarantee of $$\alpha=0.385$$, we obtain $0.2779$-approximation in polynomial time, improving over the previously best polynomial-time approximation of $0.1715$$ due to \cite{feldman2018less}. It is also worth mentioning that our algorithm is combinatorial and deterministic, which is rare for an algorithm for non-monotone submodular maximization, and enjoys a fast update time of $$O(\frac{\log k + \log (1/\alpha {\varepsilon^2})$ per element. 

   more » « less
5. Breaking the All Subsets Barrier for Min k-Cut

   https://doi.org/10.4230/LIPIcs.ICALP.2023.90  

   Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (January 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Etessami, Kousha; Feige, Uriel; Puppis, Gabriele (Ed.)

   In the Min k-Cut problem, the input is a graph G and an integer k. The task is to find a partition of the vertex set of G into k parts, while minimizing the number of edges that go between different parts of the partition. The problem is NP-complete, and admits a simple 3ⁿ⋅n^𝒪(1) time dynamic programming algorithm, which can be improved to a 2ⁿ⋅n^𝒪(1) time algorithm using the fast subset convolution framework by Björklund et al. [STOC'07]. In this paper we give an algorithm for Min k-Cut with running time 𝒪((2-ε)ⁿ), for ε > 10^{-50}. This is the first algorithm for Min k-Cut with running time 𝒪(cⁿ) for c < 2. 

   more » « less