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

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

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for minimum certificate dispersal problems

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2006年第2期E89A卷 551-558页

作者： Zheng, H Omura, S Wada, K Nagoya Inst Technol Grad Sch Engn Dept Comp Sci & Engn Nagoya Aichi 4668555 Japan

We consider a network, where a special data called certificate is issued between two users, and all certificates issued by the users in the network can be represented by a directed graph. For any two users u and v, when u needs to send a message to u securely, v's public-key is needed. The user u can obtain v's public-key using the certificates stored in u and v. We need to disperse the certificates to the users such that when a user wants to send a message to the other user securely, there are enough certificates in them to get the reliable public-key. In this paper, when a certificate graph and a set of communication requests are given, we consider the problem to disperse the certificates among the nodes in the network, such that the communication requests are satisfied and the total number of certificates stored in the nodes is minimized. We formulate this problem as MINIMUM CERTIFICATE DISPERSAL (MCD for short). We show that MCD is NP-Complete, even if its input graph is restricted to a strongly connected graph. We also present a polynomial-time 2-approximation algorithm MinPivot for strongly connected graphs, when the communication requests satisfy some restrictions. We introduce some graph classes for which MinPivot can compute optimal dispersals, such as trees, rings, and some Cartesian products of graphs.

关键词： public-key based security system certificate dispersal approximation algorithm NP-Complete

来源：评论

学校读者我要写书评

暂无评论

A constant factor approximation algorithm for boxicity of circular arc graphs

引用

DISCRETE APPLIED MATHEMATICS 2014年 178卷 1-18页

作者： Adiga, Abhijin Babu, Jasine Chandran, L. Sunil Virginia Tech Virginia Bioinformat Inst Network Dynam & Simulat Sci Lab Blacksburg VA 24061 USA Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + [log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Boxicity Cubicity Circular arc graphs approximation algorithm Normal circular arc graphs

来源：评论

学校读者我要写书评

暂无评论

A simple greedy approximation algorithm for the minimum connected -Center problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第4期31卷 1417-1429页

作者： Liang, Dongyue Mei, Liquan Willson, James Wang, Wei Xi An Jiao Tong Univ Sch Math & Stat Xian 710049 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

In this paper, we consider the connected -Center () problem, which can be seen as the classic -Center problem with the constraint of internal connectedness, i.e., two nodes in a cluster are required to be connected by an internal path in the same cluster. was first introduced by Ge et al. (ACM Trans Knowl Discov Data 2:7, 2008), in which they showed the -completeness for this problem and claimed a polynomial time approximation algorithm for it. However, the running time of their algorithm might not be polynomial, as one key step of their algorithm involves the computation of an -hard problem. We first present a simple polynomial time greedy-based -approximation algorithm for the relaxation of -the . Further, we give a -approximation algorithm for .

关键词： k-Center Greedy algorithm 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

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for P-prize-collecting Set Cover Problem

引用

Journal of the Operations Research Society of China 2023年第1期11卷 207-217页

作者： Jin-Shuang Guo Wen Liu Bo Hou School of Mathematical Sciences Hebei Key Laboratory of Computational Mathematics and ApplicationsHebei Normal UniversityShijiazhuang050024HebeiChina

In this paper,we consider the P-prize-collecting set cover(P-PCSC)problem,which is a generalization of the set cover *** this problem,we are given a set system(U,S),where U is a ground set and S⊆2U is a collection of subsets satisfying∪S∈SS=*** subset in S has a nonnegative cost,and every element in U has a nonnegative penalty cost and a nonnegative *** goal is to find a subcollection C⊆S such that the total cost,consisting of the cost of subsets in C and the penalty cost of the elements not covered by C,is minimized and at the same time the combined profit of the elements covered by C is at least P,a specified profit *** main work is to obtain a 2f+ε-approximation algorithm for the P-PCSC problem by using the primal-dual and Lagrangian relaxation methods,where f is the maximum frequency of an element in the given set system(U,S)andεis a fixed positive number.

关键词： P-prize-collecting set cover problem approximation algorithm Primal-dual Lagrangian relaxation

来源：评论

学校读者我要写书评

暂无评论

When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem

引用

JOURNAL OF HEURISTICS 2017年第5期23卷 349-366页

作者： Garcia-Diaz, Jesus Sanchez-Hernandez, Jairo Menchaca-Mendez, Ricardo Menchaca-Mendez, Rolando Inst Politecn Nacl Ctr Invest Comp Unidad Profes Adolfo Lopez Mateos Av Luis Enrique Erro S-N Mexico City DF Mexico

The vertex k-center selection problem is a well known NP-Hard minimization problem that can not be solved in polynomial time within a p < 2 approximation factor, unless P = NP . Even though there are algorithms that achieve this 2-approximation bound, they perform poorly on most benchmarks compared to some heuristic algorithms. This seems to happen because the 2-approximation algorithms take, at every step, very conservative decisions in order to keep the approximation guarantee. In this paper we propose an algorithm that exploits the same structural properties of the problem that the 2-approximation algorithms use, but in a more relaxed manner. Instead of taking the decision that guarantees a 2-approximation, our algorithm takes the best decision near the one that guarantees the 2-approximation. This results in an algorithm with a worse approximation factor (a 3-approximation), but that outperforms all the previously known approximation algorithms on the most well known benchmarks for the problem, namely, the pmed instances from OR-Lib (Beasly in J Oper Res Soc 41(11):1069-1072, 1990) and some instances from TSP-Lib (Reinelt in ORSA J Comput 3:376-384, 1991). However, the O(n(4)) running time of this algorithm becomes unpractical as the input grows. In order to improve its running time, we modified this algorithm obtaining a heuristic that outperforms not only all the previously known approximation algorithms, but all the polynomial heuristics proposed up to date.

关键词： k-Center problem approximation algorithm Dominating set Polynomial time heuristic

来源：评论

学校读者我要写书评

暂无评论

A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第2期25卷 265-278页

作者： Viet Hung Nguyen Univ Paris 06 LIP6 Paris France

We present a primal-dual aOElog(n)aOE parts per thousand-approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. The previous algorithm for the problem (V.H. Nguyen and T.T Nguyen in Int. J. Math. Oper. Res. 4(3):294-301, 2012) which is not combinatorial, is based on the Held-Karp relaxation and heuristic methods such as the Frieze et al.'s heuristic (Frieze et al. in Networks 12:23-39, 1982) or the recent Asadpour et al.'s heuristic for the ATSP (Asadpour et al. in 21st ACM-SIAM symposium on discrete algorithms, 2010). Depending on which of the two heuristics is used, it gives respectively 1+aOElog(n)aOE parts per thousand and as an approximation ratio. Our algorithm achieves an approximation ratio of aOElog(n)aOE parts per thousand which is weaker than but represents the first combinatorial approximation algorithm for the Asymmetric Prize-Collecting TSP.

关键词： Prize collecting Traveling Salesman approximation algorithm Primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：