检索结果-内蒙古大学图书馆

arXiv 2021年

作者： Angelidakis, Haris Sergeev, Ivan Westermark, Pontus Gnosis Ltd. Eth Zurich Nozomi Networks

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

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Stable approximation algorithms for the dynamic broadcast range-assignment problem

arXiv

引用

arXiv 2021年

作者： De Berg, Mark Sadhukhan, Arpan Spieksma, Frits Department of Mathematics and Computer Science TU Eindhoven Netherlands

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(

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Geometry meets vectors: approximation algorithms for multidimensional packing

arXiv

引用

arXiv 2021年

作者： Khan, Arindam Sharma, Eklavya Sreenivas, K.V.N. Department of Computer Science and Automation Indian Institute of Science Bengaluru India

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), and d nonnegative weights v1(i), v2(i), . . ., vd(i). Our goal is to get an axis-parallel non-overlapping packing of the items into square bins so that for all j ∈ [d], the sum of the jth weight of items in each bin is at most 1. This is a natural problem arising in logistics, resource allocation, and scheduling. Despite being well studied in practice, surprisingly, approximation algorithms for this problem have rarely been explored. We first obtain two simple algorithms for GVBP having asymptotic approximation ratios 6(d + 1) and 3(1 + ln(d + 1) + Ε). We then extend the Round-and-Approx (R&A) framework [3, 6] to wider classes of algorithms, and show how it can be adapted to GVBP. Using more sophisticated techniques, we obtain better approximation algorithms for GVBP, and we get further improvement by combining them with the R&A framework. This gives us an asymptotic approximation ratio of 2(1 + ln((d + 4)/2)) + Ε for GVBP, which improves to 2.919 + Ε for the special case of d = 1. We obtain further improvement when the items are allowed to be rotated. We also present algorithms for a generalization of GVBP where the items are high dimensional cuboids. Copyright © 2021, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Almost tight approximation algorithms for explainable clustering

arXiv

引用

arXiv 2021年

作者： Esfandiari, Hossein Mirrokni, Vahab Narayanan, Shyam Google Research Google Research MIT

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 humans. In this paper, we study a recent framework of explainable clustering first suggested by Dasgupta et al. [11]. Specifically, we focus on the k-means and k-medians problems and provide nearly tight upper and lower bounds. First, we provide an O(log k log log k)-approximation algorithm for explainable k-medians, improving on the best known algorithm of O(k) [11] and nearly matching the known Ω(log k) lower bound [11]. In addition, in low-dimensional spaces d log k, we show that our algorithm also provides an O(d log2 d)-approximate solution for explainable k-medians. This improves over the best known bound of O(d log k) for low dimensions [19], and is a constant for constant dimensional spaces. To complement this, we show a nearly matching Ω(d) lower bound. Next, we study the k-means problem in this context and provide an O(k log k)-approximation algorithm for explainable k-means, improving over the O(k2) bound of Dasgupta et al. and the O(dk log k) bound of [19]. To complement this we provide an almost tight Ω(k) lower bound, improving over the Ω(log k) lower bound of Dasgupta et al. Given an approximate solution to the classic k-means and k-medians, our algorithm for k-medians runs in time O(kd log2 k) and our algorithm for k-means runs in time O(k2d). Copyright © 2021, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

CLASSICAL AND QUANTUM BOUNDED DEPTH approximation algorithms

引用

QUANTUM INFORMATION & COMPUTATION 2019年第13-14期19卷 1116-1140页

作者： Hastings, Matthew B. Microsoft Res Stn Q Santa Barbara CA 93106 USA Microsoft Res Quantum Architectures & Computat Grp Redmond WA 98052 USA

We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of "local" classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2. Second, we show that this class of classical algorithms generalizes a class previously considered in the literature[1], and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances. In fact, for all but 4 choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining 4 choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of "global" classical algorithms. These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact and approximation algorithms for weighted matroid intersection

引用

MATHEMATICAL PROGRAMMING 2019年第1-2期177卷 85-112页

作者： Huang, Chien-Chung Kakimura, Naonori Kamiyama, Naoyuki PSL Ecole Normale Super CNRS Paris France Keio Univ Dept Math Yokohama Kanagawa Japan Kyushu Univ Inst Math Ind Fukuoka Fukuoka Japan

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.

关键词： Weighted matroid intersection Exact algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Near Optimal Online algorithms and Fast approximation algorithms for Resource Allocation Problems

引用

JOURNAL OF THE ACM 2019年第1期66卷 1-41页

作者： Devanur, Nikhil R. Jain, Kamal Sivan, Balasubramanian Wilkens, Christopher A. Microsoft Res 1 Microsoft Way Redmond WA 98052 USA Faira 608 State St S Kirkland WA 98033 USA Google Res 111 8th Ave New York NY 10011 USA Facebook Res 1 Hacker Way Menlo Pk CA 94025 USA

We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a 1 - epsilon fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor epsilon approaches 0 when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast epsilon approaches 0, is near optimal: We give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a 1 - epsilon fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. Further, if the algorithm is given one number per distribution, namely the optimal profit possible for each of the adversary's distribution, then we design an algorithm that achieves a 1 - epsilon fraction of the weighted average of the optimal profit of each distribution the adversary picks. In the offline setting we give a fast algorithm to solve very large linear programs (LPs) with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1 + epsilon) the mixed packing-covering problem with O(gamma m log(n/delta)/epsilon(2)) oracle calls where the constraint matrix of this LP has dimen- sion n x m, the success probability of the algorithm is 1 - delta, and gamma quantifies how significant a single request is when compared to the sum tot

关键词： Online algorithms unknown distribution approximation algorithms greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Scalability of Betweenness approximation algorithms: An Experimental Review

引用

IEEE ACCESS 2019年 7卷 104057-104071页

作者： Wandelt, Sebastian Shi, Xing Sun, Xiaoqian Beihang Univ Sch Elect & Informat Engn Beijing 100191 Peoples R China

Betweenness centrality, which measures the contribution of an individual node to the network's connectivity by counting the number of shortest paths a node appears in, is widely used for the analysis of the complex networks. The computation of exact betweenness centrality is prohibitively expensive for large networks, given a worst-case complexity of O(N * E), where N is the number of nodes and E is the number of edges in the network. Accordingly, a multitude of approximation algorithms has been proposed in the literature. Obtaining an overview of the state of the art is difficult, given a combination of numerous algorithms, parameters, and network topologies. In this paper, we report on the results of the probably largest benchmark performed in this field. Specifically, we select 100 networks with distinct topologies and scales, covering various domains. We devise and compare eight selected measures to evaluate the accuracy of the approximation, compared with the exact betweenness computation. All experiments, including those to obtain the exact betweenness values, have been performed on one computer using a single thread, in order to provide a fair comparison. We implemented typical approximation methods and report sensitivity analysis results with a variety of parameters. We find that a uniformly random sampling method, one of the earliest proposed methods in this field, still delivers the best performance, nicely addressing a sweet spot between quality and runtime complexity. In addition, we carried out robustness experiments based on the ranking order of approximated betweenness, in order to show the effect of different approximations on a real-world task. Our study aims at being a reference for choosing a betweenness approximation method, with consideration of network type, the required level of accuracy, and available computational resources.

关键词： Complex networks network topology approximation algorithms experimental review betweenness centrality

来源：评论

学校读者我要写书评

暂无评论

The ordered k-median problem: surrogate models and approximation algorithms

引用

MATHEMATICAL PROGRAMMING 2019年第1-2期177卷 55-83页

作者： Aouad, Ali Segev, Danny London Business Sch London NW1 4SA England Univ Haifa Dept Stat IL-31905 Haifa Israel

In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplicative weight, depending on its ranking (or percentile) in the ordered list of all coverage distances. While antecedent literature has focused on mathematical properties of ordered median functions, integer programming methods, various heuristics, and special cases, this problem was not studied thus far through the lens of approximation algorithms. In particular, even on simple network topologies, such as trees or line graphs, obtaining non-trivial approximation guarantees is an open question. The main contribution of this paper is to devise the first provably-good approximation algorithms for the ordered k-median problem. We develop a novel approach that relies primarily on a surrogate model, where the ordered median function is replaced by a simplified ranking-invariant functional form, via efficient enumeration. Surprisingly, while this surrogate model is Omega(n Omega(1))-hard to approximate on general metrics, we obtain an O(logn)-approximation for our original problem by employing local search methods on a smooth variant of the surrogate function. In addition, an improved guarantee of 2+E is obtained on tree metrics by optimally solving the surrogate model through dynamic programming. Finally, we show that the latter optimality gap is tight up to an O(E) term.

关键词： Location theory approximation algorithms Surrogate model Local search

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for minimum power covering problems

引用

THEORETICAL COMPUTER SCIENCE 2019年 795卷 285-300页

作者： Calinescu, Gruia Kortsarz, Guy Nutov, Zeev IIT Chicago IL 60616 USA Rutgers State Univ Camden NJ USA Open Univ Israel Raanana Israel

Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider two network design problems under the power minimization criteria. In both problems we are given a graph G = (V, E) with edge costs and a set T subset of V of terminals. The goal is to find a minimum power edge subset F subset of E such that the graph H = (V, F) satisfies some prescribed requirements. In the MIN-POWER EDGE-COVER problem, H should contain an edge incident to every terminal. Using the Iterative Randomized Rounding (IRR) method, we give an algorithm with expected approximation ratio 1.41;the ratio is reduced to 73/60 < 1.217 when T is an independent set in G. In the case of unit costs we also achieve ratio 73/60, and in addition give a simple efficient combinatorial algorithm with ratio 5/4. For all these NP-hard problems the previous best known ratio was 3/2. In the related MIN-POWER TERMINAL BACKUP problem, H should contain a path from every t is an element of T to some node in T \ {t}. We obtain ratio 3/2 for this NP-hard problem, improving the trivial ratio of 2. (C) 2019 Elsevier B.V. All rights reserved.

关键词： approximation algorithms Iterative randomized rounding Minimum power Edge-cover Terminal backup

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：