We study a variant of classical clustering formulations in the context of algorithmic fairness, known as diversity-aware clustering. In this variant we are given a collection of facility subsets, and a solution must c...
详细信息
The Dyck language, which consists of well-balanced sequences of parentheses, is one of the most fundamental context-free languages. The Dyck edit distance quantifies the number of edits (character insertions, deletion...
详细信息
The Dyck language, which consists of well-balanced sequences of parentheses, is one of the most fundamental context-free languages. The Dyck edit distance quantifies the number of edits (character insertions, deletions, and substitutions) required to make a given length-n parenthesis sequence well-balanced. RNA Folding involves a similar problem, where a closing parenthesis can match an opening parenthesis of the same type irrespective of their ordering. For example, in RNA Folding, both and )( are valid matches, whereas the Dyck language only allows () as a match. Both of these problems have been studied extensively in the literature. Using fast matrix multiplication, it is possible to compute their exact solutions in time O(n2.824) (Bringmann, Grandoni, Saha, V.-Williams, FOCS'16), and a (1 + ∈)-multiplicative approximation is known with a running time of Ω(n2.372). The impracticality of fast matrix multiplication often makes combinatorial algorithms much more desirable. Unfortunately, it is known that the problems of (exactly) computing Dyck edit distance and folding distance are at least as hard as Boolean matrix multiplication. Thereby, they are unlikely to admit truly subcubic-time combinatorial algorithms. In terms of fast approximation algorithms that are combinatorial in nature, the state of the art for Dyck edit distance is a O(log n)-factor approximation algorithm that runs in near-linear time (Saha, FOCS'14), whereas for RNA Folding only an ∈n-additive approximation in Õ(n2/∈) time (Saha, FOCS'17) is known. In this paper, we make substantial improvements to the state of the art for Dyck edit distance (with any number of parenthesis types). We design a constant-factor approximation algorithm that runs in Õ(n1.971) time (the first constant-factor approximation in subquadratic time). Moreover, we develop a (1 + ∈)-factor approximation algorithm running in Õ(n2/∈) time, which improves upon the earlier additive approximation. Finally, we design a (3 + ∈)-appr
Correlation clustering is a widely studied framework for clustering based on pairwise similarity and dissimilarity scores, but its best approximation algorithms rely on impractical linear programming relaxations. We p...
详细信息
The k-Center problem is one of the most popular clustering problems. After decades of work, the complexity of most of its variants on general metrics is now well understood. Surprisingly, this is not the case for a na...
详细信息
The k-Center problem is one of the most popular clustering problems. After decades of work, the complexity of most of its variants on general metrics is now well understood. Surprisingly, this is not the case for a natural setting that often arises in practice, namely the Euclidean setting, in which the input points are points in d, and the distance between them is the standard 2Euclidean distance. In this work, we study two Euclidean k-Center variants, the Matroid Center problem on the real line and the Robust Euclidean k-Supplier problem, and provide algorithms that improve upon the best approximation guarantees known for these problems. The Matroid Center problem on the real line is one of the rare instances of a 1-dimensional k-Center variant that is NP-hard, as shown by Chen, Li, Liang, and Wang (2016);most k- Center problems become easy when restricted to the real line. In fact, Chen et al. showed that the problem is (2 - ϵ)-hard to approximate. On the algorithmic side, only the 3-approximation algorithm for Matroid Center on general metrics by Chen et al. is known for tackling the problem. In this work, building on the classic threshold technique of Hochbaum and Shmoys (1986) and by exploiting the very special structure of real-line metrics, we improve upon the 3-approximation factor and provide a simple 2.5-approximation algorithm. We then turn to the Robust k-Supplier problem (also known as k-Supplier with outliers), which is one of the most popular k-Center variants that have been studied in the literature. It is known that the problem admits a 3-approximation on general metrics, which is tight even when there are no outliers, assuming P ≠ NP. We focus on the Euclidean setting, for which the 3 - ϵ hardness does not hold anymore. For the special case where there are no outliers, Nagarajan, Schieber and Shachnai (2020) gave a very elegant (1 + √3)-approximation algorithm for the Euclidean k-Supplier problem, thus overcoming the 3-ϵ barrier. However, their al
In the problem of active sequential hypothesis testing (ASHT), a learner seeks to identify the true hypothesis from among a known set of hypotheses. The learner is given a set of actions and knows the random distribut...
详细信息
Given an undirected graph, G, and vertices, s and t in G, the tracking paths problem is that of finding the smallest subset of vertices in G whose intersection with any s-t path results in a unique sequence. This prob...
详细信息
Let P be a set of points in d(or some other metric space), where each point p ϵ P has an associated transmission range, denoted ρ(p). The range assignment ρ induces a directed communication graph Gρ(P) on P, which ...
详细信息
Let P be a set of points in d(or some other metric space), where each point p ϵ P has an associated transmission range, denoted ρ(p). The range assignment ρ induces a directed communication graph Gρ(P) on P, which contains an edge (p, q) iff |pq| ≤ ρ(p). In the broadcast range-assignment problem, the goal is to assign the ranges such that Gρ(P) contains an arborescence rooted at a designated root node and the cost ΣpϵPρ(p)2of the assignment is minimized. We study the dynamic version of this problem. In particular, we study trade-offs between the stability of the solution-the number of ranges that are modified when a point is inserted into or deleted from P-and its approximation ratio. To this end we introduce the concept of k-stable algorithms, which are algorithms that modify the range of at most k points when they update the solution. We also introduce the concept of a stable approximation scheme, or SAS for short. A SAS is an update algorithm alg that, for any given fixed parameter ϵ > 0, is k(ϵ)-stable and that maintains a solution with approximation ratio 1+ϵ, where the stability parameter k(ϵ) only depends on ϵ and not on the size of P. We study such trade-offs in three settings. For the problem in R1, we present a SAS with k(ϵ) = O(1/ϵ). Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have k(ϵ) = Ω(1/ϵ). We also present algorithms with very small stability parameters: a 1-stable (6+2√5)-approximation algorithm- this algorithm can only handle insertions-a (trivial) 2-stable 2-approximation algorithm, and a 3-stable 1.97-approximation algorithm. For the problem in S1(that is, when the underlying space is a circle) we prove that no SAS exists. This is in spite of the fact that, for the static problem in S1, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in 1. For the problem in 2, we also prove that no SAS exists, and we present a O(
We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given n rectangular items where the ith item has width w(i), height h(i), a...
详细信息
Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal of accuracy and interpretability by h...
详细信息
In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our a...
详细信息
In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1-E)-approximate solution with a running time significantly faster than most known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. More precisely, we show that we can solve the weighted matroid intersection problem via solving W instances of the unweighted matroid intersection problem, where W is the largest given weight, assuming that all given weights are integral. Furthermore, we can find a (1-E)-approximate solution via solving O(E-1logr) instances of the unweighted matroid intersection problem, where r is the smaller rank of the two given matroids. Our algorithms make use of the weight-splitting approach of Frank (J algorithms 2(4):328-336, 1981) and the geometric scaling scheme of Duan and Pettie (J ACM 61(1):1, 2014). Our algorithms are simple and flexible: they can be adapted to special cases of the weighted matroid intersection problem, using specialized unweighted matroid intersection algorithms. In addition, we give a further application of our decomposition technique: we solve efficiently the rank-maximal matroid intersection problem, a problem motivated by matching problems under preferences.
暂无评论