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

An approximation algorithm for the maximum spectral subgraph problem

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 1880-1899页

作者： Bazgan, Cristina Beaujean, Paul Gourdin, Eric Univ Paris 09 Univ PSL CNRS LAMSADE F-75016 Paris France Orange Labs Chatillon France

Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant. amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by.. A software-defined network capable of real-time topology reconfiguration can then use an algorithm for finding such subgraph to quickly remove spreading malware threats without deploying specific security countermeasures. In this paper, we propose a novel randomized approximation algorithm based on the relaxation and rounding framework that achieves a O(log n) approximation in the case of finding a subgraph with spectral radius bounded by.. [log n,.1(G)) where.1(G) is the spectral radius of the input graph and n is the number of nodes. We combine this algorithm with a maximum matching algorithm to obtain a O(log2 n)-approximation algorithm for all values of.. We also describe how the mathematical programming formulation we give has several advantages over previous approaches which attempted at finding a subgraph with minimum spectral radius given an edge removal budget. Finally, we show that the analysis of our randomized rounding scheme is essentially tight by relating it to classical results from random graph theory.

关键词： approximation algorithm Relaxation and rounding Semidefinite programming Spectral graph theory Random graphs

来源：评论

学校读者我要写书评

暂无评论

A greedy approximation algorithm for the group Steiner problem

引用

DISCRETE APPLIED MATHEMATICS 2006年第1期154卷 15-34页

作者： Chekuri, C Even, G Kortsarz, G Lucent Bell Labs Murray Hill NJ USA Tel Aviv Univ Dept Elect Engn IL-69978 Tel Aviv Israel Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA

In the group Steiner problem we are given an edge-weighted graph G = (V, E, w) and in subsets of vertices {g(i)}(i=1)(m). Each subset gi is called a group and the vertices in boolean OR(i)g(i) are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group. We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, approximation algorithms for directed Steiner problems, J. algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant epsilon > 0, our algorithm gives an O((log Sigma(i)vertical bar g(i)vertical bar)(1+epsilon) center dot log m) approximation in polynomial time. approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of O(log vertical bar V vertical bar) in the approximation ratio, where vertical bar V vertical bar is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio

关键词： group Steiner problem tree combinatorial greedy approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for Constructing Degree-Dependent Node-Weighted Multicast Trees

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2014年第8期25卷 1976-1985页

作者： Lin, Hwa-Chun Yang, Hsiu-Ming Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan Natl Tsing Hua Univ Inst Commun Engn Hsinchu 30043 Taiwan

This paper studies the problem of constructing a minimum-cost multicast tree (or Steiner tree) in which each node is associated with a cost that is dependent on its degree in the multicast tree. The cost of a node may depend on its degree in the multicast tree due to a number of reasons. For example, a node may need to perform various processing for sending messages to each of its neighbors in the multicast tree. Thus, the overhead for processing the messages increases as the number of neighbors increases. This paper devises a novel technique to deal with the degree-dependent node costs and applies the technique to develop an approximation algorithm for the degree-dependent node-weighted Steiner tree problem. The bound on the cost of the tree constructed by the proposed approximation algorithm is derived to be (2 ln k/2 + 1) (W-T* + B), where k is the size of the set of multicast members, W-T* is the cost of a minimum-cost Steiner tree T*, and B is related to the degree-dependent node costs. Simulations are carried out to study the performance of the proposed algorithm. A distributed implementation of the proposed algorithm is presented. In addition, the proposed algorithm is generalized to solve the degree-dependent node-weighted constrained forest problem.

关键词： Multicast tree Steiner tree degree-dependent node costs approximation algorithm constrained forest

来源：评论

学校读者我要写书评

暂无评论

An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第4期32卷 1052-1067页

作者： Wang, Cui Yu, Jiguo Yu, Dongxiao Huang, Baogui Yu, Shanshan Qufu Normal Univ Sch Informat Sci & Engn Rizhao 276826 Shandong Peoples R China Univ Hong Kong Dept Comp Sci Pokfulam Hong Kong Peoples R China Shandong Univ Sch Informat Sci & Engn Jinan 250100 Peoples R China

Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and propose an approximation algorithm (A link scheduling algorithm with oblivious power assignment for the shortest link scheduling) with oblivious power assignment for better performance than GOW* proposed by Blough et al. [IEEE/ACM Trans Netw 18(6):1701-1712, 2010]. For the average scheduling length of is 1 / m of GOW*, where is the expected number of the links in the set V returned by the algorithm HyperMaxLS (Maximal links schedule under hypergraph model) and is the constant. In the worst, ideal and average cases, the ratios of time complexity of our algorithm to that of GOW* are , and , respectively. Where () is a constant called the SNR diversity of an instance G.

关键词： Wireless network Shortest link scheduling approximation algorithm Hypergraph model SINR

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the k-level capacitated facility location problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第4期20卷 361-368页

作者： Du, Donglei Wang, Xing Xu, Dachuan Beijing Univ Technol Dept Appl Math Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada

We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combinatorial) approximation algorithm with a performance factor of k + 2 + root k(2) + 2k + 5 + epsilon (epsilon > 0) for this problem.

关键词： Capacitated facility location problem approximation algorithm Local search

来源：评论

学校读者我要写书评

暂无评论

A faster, better approximation algorithm for the minimum latency problem

引用

SIAM JOURNAL ON COMPUTING 2008年第5期37卷 1472-1498页

作者： Archer, Aaron Levin, Asaf Williamson, David P. AT&T Shannon Res Lab Algorithms & Optimizat Dept Florham Pk NJ 07932 USA Hebrew Univ Jerusalem Dept Stat IL-91905 Jerusalem Israel Cornell Univ Sch Operat Res & Ind Engn Ithaca NY 14853 USA

We give a 7.18-approximation algorithm for the minimum latency problem that uses only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the k-minimum spanning tree (k-MST) problem which is called as a black box for each value of k. Their algorithm can achieve an approximation factor of 10.77 while making O(n(n + log C) log n) PCST calls, a factor of 8.98 using O(n(3)(n + log C) log n) PCST calls, or a factor of 7.18 + epsilon using n(O(1/epsilon)) log C PCST calls, via the k-MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here n denotes the number of nodes in the instance, and C is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in O(n(2)) time, the overall running time of our algorithm is O(n3 log n). We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only O(log(2) n) PCST calls, and derandomize it to obtain a deterministic algorithm with factor 7.18 + epsilon, using O(1/epsilon log(2) n) PCST calls. The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate k-MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate k-MSTs for all values of k, even though we have them only for some values of k that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem.

关键词： minimum latency problem traveling repairman approximation algorithm Lagrangian relaxation prize-collecting Steiner tree

来源：评论

学校读者我要写书评

暂无评论

A primal-dual approximation algorithm for the k-prize-collecting minimum power cover problem

引用

OPTIMIZATION LETTERS 2022年第8期16卷 2373-2385页

作者： Liu, Xiaofei Li, Weidong Xie, Runtao Yunnan Univ Sch Informat Sci & Engn Kunming Yunnan Peoples R China Peking Univ Sch EECS Beijing Peoples R China Yunnan Univ Sch Math & Stat Kunming Yunnan Peoples R China

In this paper, we introduce the k-prize-collecting minimum power cover problem (k-PCPC). In this problem, we are given a point set V, a sensor set S on a plane and a parameter k with k <= |V|. Each sensor can adjust its power and the covering range of sensor s with power p(D(s, r (s))) is a disk D(s, r (s)), where r (s) is the radius of disk D(s, r (s)) and p(D(s, r (s))) = c center dot r (s)(alpha). The k-PCPC determines a disk set F such that at least k points are covered, where the center of any disk in F is a sensor. The objective is to minimize the total power of the disk set F plus the penalty of R, where R is the set of points that are not covered by F. This problem generalizes the well-known minimum power cover problem, minimum power partial cover problem and prize collecting minimum power cover problem. Our main result is to present a novel two-phase primal-dual algorithm for the k-PCPC with an approximation ratio of at most 3(alpha).

关键词： Power cover k-prize-collection Primal-dual approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for Optimal Clique Cover Delivery in Coded Caching

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2019年第7期67卷 4683-4695页

作者： Asghari, Seyed Mohammad Ouyang, Yi Nayyar, Ashutosh Avestimehr, A. Salman Univ Southern Calif Dept Elect Engn Los Angeles CA 90089 USA Preferred Networks Amer Inc Berkeley CA 94704 USA

Coded caching can significantly reduce the communication bandwidth requirement for satisfying users' demands by utilizing the multicasting gain among multiple users. Most existing works assume that the users follow the prescriptions for content placement made by the system. However, users may prefer to decide what files to cache. To address this issue, we consider a network consisting of a file server connected through a shared link to K users, each equipped with a cache which has been already filled arbitrarily. Given an arbitrary content placement, the goal is to find a delivery strategy for the server that minimizes the load of the shared link. In this paper, we focus on a specific class of coded multicasting delivery schemes known as the "clique cover delivery scheme." We first formulate the optimal clique cover delivery problem as a combinatorial optimization problem. Using a connection with the weighted set cover problem, we propose an approximation algorithm and show that it provides an approximation ratio of (1 + logK), while the approximation ratio for the existing coded delivery schemes is linear in K. Numerical simulations show that our proposed algorithm provides a considerable bandwidth reduction over the existing coded delivery schemes for almost all content placement schemes.

关键词： Caching coded multicast clique cover delivery weighted set cover approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved approximation algorithm for the Most Points Covering Problem

引用

THEORY OF COMPUTING SYSTEMS 2012年第3期50卷 545-558页

作者： Ghasemalizadeh, Hossein Razzazi, Mohammadreza Amirkabir Univ Technol Dept Comp Engn & Informat Technol SSRD Lab Tehran Iran Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran

In this paper we present a polynomial time approximation scheme for the most points covering problem. In the most points covering problem, n points in R-2, r > 0, and an integer m> 0 are given and the goal is to cover the maximum number of points with m disks with radius r. The dual of the most points covering problem is the partial covering problem in which n points in R-2 are given, and we try to cover at least p <= n points of these n points with the minimum number of disks. Both these problems are NP-hard. To solve the most points covering problem, we use the solution of the partial covering problem to obtain an upper bound for the problem and then we generate a valid solution for the most points covering problem by a careful modification of the partial covering solution. We first present an improved approximation algorithm for the partial covering problem which has a better running time than the previous algorithm for this problem. Using this algorithm, we attain a (1 - 2 epsilon/1+)-approximation algorithm for the most points covering problem. The running time of our algorithm is O((1 + epsilon) mn + epsilon(-1)n(4)root 2(epsilon-1) + 2) which is polynomial with respect to both m and n, whereas the previously known algorithm for this problem runs in O(n log n + n epsilon(-6m+6) log(1/epsilon)) which is exponential regarding m.

关键词： Geometric covering Most points covering Partial covering approximation algorithm Computational geometry

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the k-prize-collecting multicut on a tree problem

引用

THEORETICAL COMPUTER SCIENCE 2020年 844卷 26-33页

作者： Hou, Xin Liu, Wen Hou, Bo Hebei Normal Univ Sch Math Sci Shijiazhuang 050024 Hebei Peoples R China

In this paper, we consider the k-prize-collecting multicut on a tree (k-PCM(T)) problem. In this problem, we are given an undirected tree T = (V, E), a set of m distinct pairs of vertices P = {(s(1), t(1)), . . . , (s(m), t(m))} and a parameter k with k <= m. Every edge in E has a nonnegative cost c(e). Every pair (s(i), t(i)) in P has a nonnegative penalty cost pi(i). Our goal is to find a multicut M that separates at least k pairs in P such that the total cost, including the edge cost of the multicut M and the penalty cost of the pairs not separated by M, is minimized. This problem generalizes the well-known multicut on a tree problem. Our main work is to present a (4 + epsilon)-approximation algorithm for the k-PCM(T) problem via the methods of primal-dual and Lagrangean relaxation, where s is any fixed positive number. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Multicut k-prize-collecting multicut approximation algorithm Primal-dual algorithm Lagrange relaxation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：