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

Programmable device deployment for efficient network function offloading

COMPUTER NETWORKS 2024年 239卷

作者： Tu, Huaqing Zhao, Gongming Xu, Hongli Qiao, Chunming Zhejiang Lab Changsha Peoples R China Univ Sci & Technol China Sch Comp Sci & Technol Hefei Peoples R China Univ Sci & Technol China Suzhou Inst Adv Res Hefei Peoples R China SUNY Buffalo Dept Comp Sci & Engn Buffalo NY USA

Network functions (NFs) play an important role in ensuring network security and performance. To improve the NF throughput performance, an emerging method is to offload NFs on programmable devices, bringing orders-of-magnitude improvements. A primary task for efficient NF offloading is how to deploy programmable devices (e.g., programmable switches) for network upgrades. Although programmable switches have powerful computing resources, their memory resources are usually limited, which poses a challenge of offloading stateful NFs (e.g., load balancer, NAT) with a large-size memory requirement. A promising solution to break the memory limitation is using external memory (e.g., on commodity servers) with the help of remote direct memory access (RDMA) supported by SmartNIC. Therefore, this paper studies the problem of upgrading networks by replacing legacy switches with programmable switches and equipping commodity servers with SmartNICs so that NFs can be offloaded on programmable switches with external memory expansion. We prove that this problem is NP-Hard, and there is no polynomial-time algorithm with an approximation ratio of (1 - e) center dot ln h, where e is an arbitrarily small value, and h is the total number of requests in the network. Then we design an efficient algorithm with an approximation ratio of 2.5 center dot H(m center dot n), where m is the number of NF types, n is the maximum number of requests through a switch, and H(m center dot n) is the (m center dot n)th harmonic number. The simulation results show that our solution can reduce the upgrade cost by about 70% compared with the state-of-the-art approaches while preserving the same system throughput.

关键词： Network function offloading Programmable devices approximation algorithm Network upgrade

来源：评论

学校读者我要写书评

暂无评论

Minimization Problems with Non-Submodular Cover Constraint

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第5期40卷 2340012-2340012页

作者： Wang, Wenqi Liu, Zhicheng Du, Donglei Shi, Peihao Zhang, Xiaoyan Nanjing Normal Univ Sch Math Sci Nanjing 210023 Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 9Y2 Canada Ind Technol Res Inst Co Ltd Nanjing Kinghua Operat Res & ArtificialIntelligenc Nanjing 210035 Peoples R China

The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovasz extension, we devise greedy and primal-dual approximation algorithms for these problems.

关键词： approximation algorithm submodular function combinatorial optimization greedy algorithm primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating the directed path partition problem ☆

引用

INFORMATION AND COMPUTATION 2024年 297卷

作者： Chen, Yong Chen, Zhi-Zhong Kennedy, Curtis Lin, Guohui Xu, Yao Zhang, An Hangzhou Dianzi Univ Dept Math Hangzhou Peoples R China Tokyo Denki Univ Div Informat Syst Design Saitama Japan Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Georgia Southern Univ Dept Comp Sci Statesboro GA USA

Given a digraph G = (V, E), the k-path partition problem aims to find a minimum collection of vertex-disjoint directed paths, of order at most k, to cover all the vertices. The problem has various applications. Its special case on undirected graphs is NP-hard when k >= 3, and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k/2-approximation algorithm, based on a novel concept of enlarging walk to minimize the number of singletons. Secondly, for k = 3, we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13/9-approximation algorithm. Lastly, for any k >= 7, we present an improved (k + 2)/3-approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Path partition Digraph Alternating walk Enlarging walk Path -cycle cover approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating the multiple-depot multiple-terminal Hamiltonian path problem

引用

DISCRETE OPTIMIZATION 2019年 34卷 100545-000页

作者： Yang, Yichen Liu, Zhaohui East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

In this paper, we study a multiple-terminal extension of the classic Hamiltonian path problem where m salesmen are initially located at different depots and finally stopped at different terminals. To the best of our knowledge, only 2-approximation algorithm is available in the literature. For arbitrary m >= 2, we first present a Christofides-like heuristic with a tight approximation ratio of 2-1/2m+1. Besides, we also develop a (5/4 + epsilon)-approximation algorithm by divide-and-conquer technique. The (5/4 + epsilon) -approximation algorithm runs in polynomial time for fixed m and E. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Hamiltonian path problem approximation algorithm Constrained forest Matroid

来源：评论

学校读者我要写书评

暂无评论

Optimal Base Station Placement in Wireless Sensor Networks

引用

ACM TRANSACTIONS ON SENSOR NETWORKS 2009年第4期5卷 32-32页

作者： Shi, Yi Hou, Y. Thomas Virginia Polytech Inst & State Univ Bardley Dept Elect & Comp Engn Blacksburg VA 24061 USA

Base station location has a significant impact on network lifetime performance for a sensor network. For a multihop sensor network, this problem is particularly challenging due to its coupling with data routing. This article presents an approximation algorithm that can guarantee (1-epsilon)-optimal network lifetime performance for base station placement problem with any desired error bound epsilon > 0. The proposed (1-epsilon)-optimal approximation algorithm is based on several novel techniques that makes it possible to reduce an infinite search space to a finite-element search space for base station location. The first technique used in this reduction is to discretize cost parameter (associated with energy consumption) with performance guarantee. Subsequently, the continuous search space can be broken up into a finite number of subareas. The second technique is to exploit the cost property of each subarea and represent it by a novel notion called fictitious cost point, each with guaranteed cost bounds. We give a proof that the proposed base station placement algorithm is (1-epsilon)-optimal. This approximation algorithm is simpler and faster than a state-of-the-art algorithm and represents the best known result to the base station placement problem.

关键词： algorithms Performance Theory approximation algorithm base station placement network lifetime sensor network

来源：评论

学校读者我要写书评

暂无评论

Approximating Gromov-Hausdorff distance in Euclidean space

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2024年 116卷

作者： Majhi, Sushovan Vitter, Jeffrey Wenk, Carola Univ Calif Berkeley Sch Informat Berkeley CA 94720 USA Univ Mississippi Dept Comp & Informat Sci University MS 38677 USA Tulane Univ Dept Comp Sci New Orleans LA 70118 USA

The Gromov-Hausdorff distance (dGH) proves to be a useful distance measure between shapes. In order to approximate dGH for X, Y & SUB;Rd, we look into its relationship with dH,iso, the infimum Hausdorff distance under Euclidean isometries. As already known for dimension d & GE;2, dH,iso cannot be bounded above by a constant factor times dGH. For d = 1, however, we prove that dH,iso & LE;54dGH. We also show that the bound is tight. In effect, for X, Y & SUB;R with at most n points, this gives rise to an O (n log n)-time algorithm to approximate dGH(X, Y) with an approximation factor of (1 + 1 �. 4 & COPY;2023 Elsevier B.V. All rights reserved.

关键词： Gromov-Hausdorff distance approximation algorithm Abstract distance measures Shape comparison

来源：评论

学校读者我要写书评

暂无评论

A Method of Lower and Upper Solutions for Control Problems and Application to a Model of Bone Marrow Transplantation

引用

INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE 2023年第3期33卷 409-418页

作者： Parajdi, Lorand Gabriel Precup, Radu Haplea, Ioan Stefan West Virginia Univ Dept Math POB 6201 Morgantown WV 26506 USA Babes Bolyai Univ Dept Math M Kogalniceanu St 1 Cluj Napoca 400084 Romania Babeş Bolyai Univ Inst Adv Studies Sci & Technol M Kogalniceanu St 1 Cluj-napoca 400084 Cluj Romania Romanian Acad Tiberiu Popoviciu Inst Numer Anal POB 68-1 Cluj Napoca 400110 Romania Iuliu Hatieganu Univ Med & Pharm Fac Med Dept Internal Med Victor Babes St 8 Cluj Napoca 400012 Romania

A lower and upper solution method is introduced for control problems related to abstract operator equations. The method is illustrated on a control problem for the Lotka-Volterra model with seasonal harvesting and app... 详细信息

关键词： control problem lower and upper solutions fixed point approximation algorithm numerical solution medical application

来源：评论

学校读者我要写书评

暂无评论

Improving energy efficiency in colocation data centers for demand response

引用

SUSTAINABLE COMPUTING-INFORMATICS & SYSTEMS 2021年第PartB期29卷

作者： Chi, Ce Zhang, Fa Ji, Kaixuan Marahatta, Avinab Liu, Zhiyong Chinese Acad Sci Inst Comp Technol High Performance Comp Res Ctr Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

Colocation data centers (colocations, for short) are developing rapidly and have become ideal participants for emergency demand response (EDR) programs. However, even colocation operators wish to save energy, they cannot achieve energy reduction without coordination from the tenants, because the servers in the colocations are owned and operated by the tenants. To solve the ?uncoordinated relationship? issue between operators and tenants, some works have been done by way of incentivizing the tenants to reduce the energy consumption of their servers. However, apart from servers, the power consumption of the cooling system also accounts for a large portion in a colocation, which should be optimized as well. Unfortunately, the servers and the cooling system are controlled by tenants and operators separately in colocations, and thus ?uncoordinated relationship? issue also exists between IT and cooling systems. In this paper, coarse-grained and fine-grained incentive mechanisms are proposed to solve these problems. approximation algorithms are developed to optimize the energy-saving problems. Furthermore, Vickrey?Clarke?Groves (VCG) theory is introduced into our incentive mechanism design to guarantee the feasibility and truthfulness of the two mechanisms. Trace-driven simulations are performed to validate the effectiveness of the two incentive mechanisms. The results show that compared with the existing incentive mechanisms, up to 20.50% of the energy-saving cost can be reduced in the coarse-grained mechanism and 28.34% of the cost reduction can be achieved in the fine-grained mechanism.

关键词： Colocation data center Mechanism design Energy efficiency approximation algorithm Truthfulness

来源：评论

学校读者我要写书评

暂无评论

Quasi-linear time heuristic to solve the Euclidean traveling salesman problem with low gap

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2024年 82卷

作者： Formella, Arno Univ Vigo Vigo Spain

The traveling salesman problem (TSP) is a well studied NP-hard optimization problem. We present a novel heuristic to find approximate solutions for the case of the TSP with Euclidean metric. Our pair-center algorithm runs in quasi-linear time and on linear space. In practical experiments on a variety of well known benchmarks the algorithm shows linearithmic (i.e., O(n ( n log n ) ) runtime. The solutions found by the pair-center algorithm are very good on smaller problem instances, and better than those generated by any other heuristic with at most quadratic runtime. Eventually, the average gap of the pair-center algorithm on all benchmark instances with less than 1001 points is 0.94% and for all instances with more than 1000 points up to 100 million points is 4.57%.

关键词： Euclidean TSP Computational geometry Heuristic approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Max-Weighted Point Sweep Coverage on Lines

引用

SENSORS 2021年第4期21卷 1457-1457页

作者： Liang, Dieyan Shen, Hong Sun Yat Sen Univ Sch Comp Sci & Engn Guangzhou 510275 Peoples R China

As an important application of wireless sensor networks (WSNs), deployment of mobile sensors to periodically monitor (sweep cover) a set of points of interest (PoIs) arises in various applications, such as environmental monitoring and data collection. For a set of PoIs in an Eulerian graph, the point sweep coverage problem of deploying the fewest sensors to periodically cover a set of PoIs is known to be Non-deterministic Polynomial Hard (NP-hard), even if all sensors have the same velocity. In this paper, we consider the problem of finding the set of PoIs on a line periodically covered by a given set of mobile sensors that has the maximum sum of weight. The problem is first proven NP-hard when sensors are with different velocities in this paper. Optimal and approximate solutions are also presented for sensors with the same and different velocities, respectively. For M sensors and N PoIs, the optimal algorithm for the case when sensors are with the same velocity runs in O(MN) time;our polynomial-time approximation algorithm for the case when sensors have a constant number of velocities achieves approximation ratio 1/2;for the general case of arbitrary velocities, 1/2 alpha and 1/2(1-1/e) approximation algorithms are presented, respectively, where integer alpha >= 2 is the tradeoff factor between time complexity and approximation ratio.

关键词： WSN mobile sensors sweep coverage approximation algorithm combinatorial mathematics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：