We give a poly-time algorithm for the k-edge-connected spanning subgraph (k-ECSS) problem that returns a solution of cost no greater than the cheapest (k + 10)-ECSS on the same graph. Our approach enhances the iterati...
详细信息
ISBN:
(纸本)9798400703836
We give a poly-time algorithm for the k-edge-connected spanning subgraph (k-ECSS) problem that returns a solution of cost no greater than the cheapest (k + 10)-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems. Our guarantees improve upon the best-known approximation factor of 2 for k-ECSS whenever the optimal value of (k+10)-ECSS is close to that of k-ECSS. This is a property that holds for the closely related problem k-edge-connected spanning multi-subgraph k-ECSM), which is identical to k-ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a (1 + O(1/k))-approximation algorithm for k-ECSM, which resolves a conjecture of Pritchard and improves upon a recent (1 + O(1/root k))-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for k-ECSM, showing that our approximation ratio is tight up to the constant factor in O(1/k), unless P = NP.
While the search for quantum advantage typically focuses on speed-ups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data ...
详细信息
ISBN:
(纸本)9798400703836
While the search for quantum advantage typically focuses on speed-ups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been restricted to specially-constructed problems [Le Gall, SPAA '06] or polynomial advantage [Kallaugher, FOCS '21]. We show an exponential quantum space advantage for the maximum directed cut problem. This is the first known exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem in any setting. Our quantum streaming algorithm 0.4844-approximates the value of the largest directed cut in a graph stream with n vertices using polylog(n) space, while previous work by Chou, Golovnev, and Velusamy [FOCS '20] implies that obtaining an approximation ratio better than 4/9 approximate to 0.4444 requires Omega(root n) space for any classical streaming algorithm. Our result is based on a recent ($) over tilde(root n) space classical streaming approach by Saxena, Singer, Sudan, and Velusamy [FOCS '23], with an additional improvement in the approximation ratio due to recent work by Singer [APPROX '23].
This paper proves that a simple greedy algorithm for finding a maximal independent set in a graph is also a randomized 2-approximation algorithm for weighted vertex cover. The unweighted version of the algorithm has e...
详细信息
ISBN:
(纸本)9781611977936
This paper proves that a simple greedy algorithm for finding a maximal independent set in a graph is also a randomized 2-approximation algorithm for weighted vertex cover. The unweighted version of the algorithm has existed for decades as a maximal independent set algorithm, but was not previously known to approximate vertex cover. This result leads to several new insights and simplified algorithms for different graph problems as corollaries. This includes a simple O(log n)-round parallel algorithm for vertex cover, simplified approximation algorithms for certain edge deletion problems, connections to correlation clustering, and insights for list heuristic algorithms for vertex cover.
Hyperspectral super-resolution based on coupled Tucker decomposition has been recently considered in the remote sensing community. The state-of-the-art approaches did not fully exploit the coupling of information cont...
详细信息
ISBN:
(数字)9781665496209
ISBN:
(纸本)9781665496209
Hyperspectral super-resolution based on coupled Tucker decomposition has been recently considered in the remote sensing community. The state-of-the-art approaches did not fully exploit the coupling of information contained in hyperspectral and multispectral images of the same scene. This paper proposes a new algorithm that overcomes this limitation. It accounts for both the high-resolution and the low-resolution information in the model by solving a set of least-squares problems. In addition, we provide exact recovery conditions for the super-resolution image in the noiseless case. Our simulations show that the proposed algorithm achieves very good reconstruction quality with a very low computational complexity.
The Shapley value, which is arguably the most popular approach for assigning a meaningful contribution value to players in a cooperative game, has recently been used intensively in explainable artificial intelligence....
详细信息
ISBN:
(纸本)1577358872
The Shapley value, which is arguably the most popular approach for assigning a meaningful contribution value to players in a cooperative game, has recently been used intensively in explainable artificial intelligence. Its meaningfulness is due to axiomatic properties that only the Shapley value satisfies, which, however, comes at the expense of an exact computation growing exponentially with the number of agents. Accordingly, a number of works are devoted to the efficient approximation of the Shapley value, most of them revolve around the notion of an agent's marginal contribution. In this paper, we propose with SVARM and Stratified SVARM two parameter-free and domain-independent approximation algorithms based on a representation of the Shapley value detached from the notion of marginal contribution. We prove unmatched theoretical guarantees regarding their approximation quality and provide empirical results including synthetic games as well as common explainability use cases comparing ourselves with state-of-the-art methods.
We consider the Min-Sum k-Clustering (k k-MSC) problem. Given a set of points in a metric which is represented by an edge-weighted graph G = ( V, E ) and a parameter k , the goal is to partition the points V into k cl...
详细信息
We consider the Min-Sum k-Clustering (k k-MSC) problem. Given a set of points in a metric which is represented by an edge-weighted graph G = ( V, E ) and a parameter k , the goal is to partition the points V into k clusters such that the sum of distances between all pairs of the points within the same cluster is minimized. The k-MSC problem is known to be APX-hard on general metrics. The best known approximation algorithms for the problem obtained by Behsaz et al. (2019) achieve an approximation ratio of O (log |V V |) ) in polynomial time for general metrics and an approximation ratio 2 + e in quasi-polynomial time for metrics with bounded doubling dimension. No approximation schemes for k-MSC (when k is part of the input) is known for any non-trivial metrics prior to our work. In fact, most of the previous works rely on the simple fact that there is a 2-approximate reduction from k-MSC to the balanced k-median problem and design approximation algorithms for the latter to obtain an approximation for k-MSC. In this paper, we obtain the first Quasi-Polynomial Time approximation Schemes (QPTAS) for the problem on metrics induced by graphs of bounded treewidth, graphs of bounded highway dimension, graphs of bounded doubling dimensions (including fixed dimensional Euclidean metrics), and planar and minor-free graphs. We bypass the barrier of 2 for k-MSC by introducing a new clustering problem, which we call min-hub clustering, which is a generalization of balanced k-median and is a trade off between center-based clustering problems (such as balanced k-median) and pair-wise clustering (such as Min-Sum k-clustering). We then show how one can find approximation schemes for Min-hub clustering on certain classes of metrics.
Given a metric space (V, d) along with an integer k, the k-Median problem asks to open k centers C subset of V to minimize Sigma(v is an element of V) d(v, C), where d(v, C) := mi(n is an element of C) d(v, c). While ...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
Given a metric space (V, d) along with an integer k, the k-Median problem asks to open k centers C subset of V to minimize Sigma(v is an element of V) d(v, C), where d(v, C) := mi(n is an element of C) d(v, c). While the best-known approximation ratio 2.613 holds for the more general supplier version where an additional set F subset of V is given with the restriction C subset of F, the best known hardness for these two versions are 1+1/e approximate to 1.36 and 1+2/e approximate to 1.73 respectively, using the same reduction from Maximum k-Coverage. We prove the following two results separating them. 1. We give a 1.546-parameterized approximation algorithm that runs in time f(k)n(O(1)). Since 1+ 2/e is proved to be the optimal approximation ratio for the supplier version in the parameterized setting, this result separates the original k-Median from the supplier version. 2. We prove a 1.416-hardness for polynomial-time algorithms assuming the Unique Games Conjecture. This is achieved via a new finegrained hardness of Maximum k-Coverage for small set sizes. Our upper bound and lower bound are derived from almost the same expression, with the only difference coming from the well-known separation between the powers of LP and SDP on (hypergraph) vertex cover.
We present an algorithm for detecting saccadic (fast) eye movements from electrooculogram data based on approximation using a parametric saccade model. The algorithm is based on a sliding window approximation on two c...
详细信息
In this paper, we consider differential approximability of the traveling salesman problem (TSP). The differential approximation ratio was proposed by Demange and Paschos in 1996 as an approximation criterion that is i...
详细信息
ISBN:
(纸本)9783031203497;9783031203503
In this paper, we consider differential approximability of the traveling salesman problem (TSP). The differential approximation ratio was proposed by Demange and Paschos in 1996 as an approximation criterion that is invariant under affine transformation of the objective function. We show that TSP is 3/4-differential approximable, which improves the currently best known bound 3/4- O(1/n) due to Escoffier and Monnot in 2008, where n denotes the number of vertices in the given graph.
Neural networks with finitely many fixed weights have the universal approximation property under certain conditions on compact subsets of the ������-dimensional Euclidean space, where approximation process is consider...
详细信息
Neural networks with finitely many fixed weights have the universal approximation property under certain conditions on compact subsets of the ������-dimensional Euclidean space, where approximation process is considered. Such conditions were delineated in our paper [26]. But for many compact sets it is impossible to approximate multivariate functions with arbitrary precision and the question on estimation or efficient computation of approximation error arises. This paper provides an explicit formula for the approximation error of single hidden layer neural networks with two fixed weights.
暂无评论