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

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 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-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

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

PENGRAV: a practical polynomial time algorithm for optimizing the engraving path of an automatic engraving machine using a 3/2 approximation algorithm

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2022年第5-6期123卷 1721-1732页

作者： Eapen, Neeta A. Heckendorn, Robert B. Univ Idaho Dept Comp Sci Moscow ID 83844 USA

Automatic engraving machines have several industrial applications, such as nameplates, identification codes, and bar code engraving. It can also be used for engraving messages or pictures on decorative items in homes. Additionally, the proposed algorithm can be extended for obtaining the paths for 3D printers. The engraving process happens when the designs, messages, or pictures are carved into any item. The cost of engraving can be optimized by minimizing the movements of the automatic engraving machine. The movements include engraving motions and air motions. This work proposes a fast algorithm for obtaining the engraving path that guarantees the air motions are at most 150% of the optimal. Optimum engraving paths are commonly obtained using exponential time algorithms. The proposed algorithm is a 3/2 approximation algorithm that obtains the engraving path in polynomial time. The experimental results indicate that the proposed algorithm computes an efficient engraving path in a short time.

关键词： Automatic engraving Automatic plotting Polynomial time approximation algorithm Engraving path optimization 3D printer

来源：评论

学校读者我要写书评

暂无评论

A Connectivity-Aware approximation algorithm for Relay Node Placement in Wireless Sensor Networks

引用

IEEE SENSORS JOURNAL 2016年第2期16卷 515-528页

作者： Ma, Chaofan Liang, Wei Zheng, Meng Sharif, Hamid Chinese Acad Sci Key Lab Networked Control Syst Shenyang 110016 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Univ Nebraska Dept Comp & Elect Engn Omaha NE 68182 USA

In two-tiered wireless sensor networks (WSNs), relay node placement is one of the key factors impacting the network energy consumption and the system overhead. In this paper, a novel connectivity-aware approximation algorithm for relay node placement in the WSNs is proposed to offer a major step forward in saving system overhead. In particular, a unique local search approximation algorithm (LSAA) is introduced to solve the relay node single cover (RNSC) problem. In this proposed LSAA approach, the sensor nodes are allocated into groups and then a local set cover (SC) for each group is achieved by a local search algorithm. The union set of all the local SCs constitutes a SC of the RNSC problem. The approximation ratio and the time complexity of the LSAA are analyzed by rigorous proof. In addition, the LSAA approach has been extended to solve the relay node double cover problem. Then, a relay location selection algorithm (RLSA) is proposed to utilize the resulting SC from the LSAA in combining RLSA with the minimum spanning tree heuristic to build the high-tier connectivity. As the RLSA searches for a nearest location to the sink node for each relay node, the high-tier network built by the RLSA becomes denser than that by existing works. As a result, the number of added relay nodes for building the connectivity of the high-tier WSN can be significantly saved. Simulation results clearly demonstrate that the proposed LSAA outperforms the approaches reported in literature and the RLSA-based algorithm can noticeably save relay nodes newly deployed for the high-tier connectivity.

关键词： Wireless sensor networks relay node placement geometric disc cover network connectivity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A 3/4-approximation algorithm for multiple subset sum

引用

JOURNAL OF HEURISTICS 2003年第2期9卷 99-111页

作者： Caprara, A Kellerer, H Pferschy, U Univ Bologna DEIS I-40136 Bologna Italy Graz Univ Dept Stat & Operat Res A-8010 Graz Austria

The Multiple Subset Sum Problem (MSSP) is the variant of bin packing in which the number of bins is given and one would like to maximize the overall weight of the items packed in the bins. The problem is also a special case of the multiple knapsack problem in which all knapsacks have the same capacity and the item profits and weights coincide. Recently, polynomial time approximation schemes have been proposed for MSSP and its generalizations, see A. Caprara, H. Kellerer, and U. Pferschy (SIAM J. on Optimization, Vol. 11, pp. 308-319, 2000;Information Processing Letters, Vol. 73, pp. 111-118, 2000), C. Chekuri and S. Khanna (Proceedings of SODA 00, 2000, pp. 213-222), and H. Kellerer (Proceedings of APPROX, 1999, pp. 51-62). However, these schemes are only of theoretical interest, since they require either the solution of huge integer linear programs, or the enumeration of a huge number of possible solutions, for any reasonable value of required accuracy. In this paper, we present a polynomial-time 3/4-approximation algorithm which runs fast also in practice. Its running time is linear in the number of items and quadratic in the number of bins. The "core" of the algorithm is a procedure to pack triples of "large" items into the bins. As a by product of our analysis, we get the approximation guarantee for a natural greedy heuristic for the 3-Partitioning Problem.

关键词： multiple subset sum approximation algorithm 3-partitioning

来源：评论

学校读者我要写书评

暂无评论

A 3/2-approximation algorithm for two-machine flow-shop sequencing subject to release dates

引用

DISCRETE APPLIED MATHEMATICS 2001年第1-3期114卷 255-271页

作者： Kashyrskikh, KN Potts, CN Sevastianov, SV Sobolev Inst Math Novosibirsk 630090 Russia Univ Southampton Fac Math Sci Southampton S017 1BJ Hants England Novosibirsk State Univ Novosibirsk 630090 Russia

The two-machine flow-shop sequencing problem with arbitrary release dates of jobs and the minimum makespan criterion is considered. The problem is known to be NP-hard, and the best-known approximation algorithms are those of Potts (Math. Oper. Res. 10 (1985) 576) with a worst-case performance ratio of 5/3 and running time O(n(3) log n), and a polynomial time approximation scheme of Hall (Proceedings of the 36th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. press, Los Alamitos, 1995, pp. 82-91.) that can generate solutions arbitrary close to the optimum but with a high-time requirement. In this paper, we modify Potts' algorithm so that its worst-case performance ratio is reduced to 3/2, but its running time remains O(n(3) log n). (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： scheduling flow shop release dates approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：