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

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

来源：评论

学校读者我要写书评

暂无评论

On the difference set of two transductions

引用

THEORETICAL COMPUTER SCIENCE 2024年 1016卷

作者： Konstantinidis, Stavros Moreira, Nelma Reis, Rogerio Sebej, Juraj St Marys Univ Math & CS 923 Robie Str Halifax NS B3H 3C3 Canada Univ Porto Fac Ciencias CMUP & DM DCC Rua Campo Alegre P-4169007 Porto Portugal Safarik Univ Inst Comp Sci Fac Sci Kosice Slovakia

The difference set ds,t of two (nondeterministic, in general) transducers s, t is the set of all input words for which the output sets of the two transducers are not equal. When the two transducers realize homomorphisms, their difference set is the complement of the well known equality set of the two homomorphisms. However, we show that transducer difference sets result in Chomskylike classes of languages that are different than the classes resulting from equality sets. We also consider the following word problem: given transducers s, t and input w, tell whether the output sets s(w) and t(w) are different. In general the problem is PSPACE-complete, but it becomes NP-complete when at least one of the given transducers has finite outputs. We also provide a PRAX (polynomial randomized approximation) algorithm for the word problem as well as for the NFA (in)equivalence problem. Our presentation of PRAX algorithms improves the original presentation.

关键词： Transducer Difference set Equality set Counter machine approximation algorithm Randomized algorithm NFA equivalence

来源：评论

学校读者我要写书评

暂无评论

New algorithms for a Simple Measure of Network Partitioning 17th

New Algorithms for a Simple Measure of Network Partitioning

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Zhao, Xueyang Yan, Binghao Zhang, Peng Shandong Univ Sch Software Jinan 250101 Shandong Peoples R China

ISBN: (纸本)9783031203497;9783031203503

Partitioning a network into k pieces is a fundamental problem in network science. A simple measure of partitioning a network is provided by the Max k-Uncut problem. Given an n-vertex undirected graph G with nonnegative weights defined on edges, and a positive integer k, the Max k-Uncut problem asks to find a k-partition of the vertices of G to maximize the total weight of edges that are not in the cut. This problem is the complement of the classic Min k-Cut problem, and has close relation to many combinatorial optimization problems, including the famous Densest k-Subgraph problem. In this paper, we propose a greedy approximation algorithm for the Max k-Uncut problem with performance ratio 1 - 2(k-1)/n. The algorithm is very simple, which consists of only k - 1 min cut computations. The algorithm has fast running time O(kn(2)) and is hence implementable. The experimental results show that the algorithm has excellent practical performance.

关键词： Max k-Uncut Network partitioning Graph algorithm approximation algorithm Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Joint Caching and Routing in Cache Networks with Arbitrary Topology 42

Joint Caching and Routing in Cache Networks with Arbitrary T...

引用

42nd IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Xie, Tian Thakkar, Sanchal He, Ting McDaniel, Patrick Burke, Quinn Penn State Univ University Pk PA 16802 USA

ISBN: (数字)9781665471770

ISBN: (纸本)9781665471770

In-network caching and flexible routing are two of the most celebrated advantages of next generation network infrastructures. Yet few solutions are available for jointly optimizing caching and routing that provide performance guarantees for an arbitrary topology. We take a holistic approach towards this fundamental problem by analyzing its complexity in all the cases and developing polynomial-time algorithms with approximation guarantees in important special cases. We also reveal the fundamental challenge in achieving guaranteed approximation in the general case and propose an alternating optimization algorithm with good performance and fast convergence. Our algorithms have demonstrated superior performance in both routing cost and congestion compared to the state-of-the-art solutions in evaluations based on real topology and request traces.

关键词： cache network joint caching and routing unsplittable flow problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas 15th

Incomplete List Setting of the Hospitals/Residents Problem w...

引用

15th International Symposium on algorithmic Game Theory (SAGT)

作者： Makino, Kazuhisa Miyazaki, Shuichi Yokoi, Yu Kyoto Univ Kyoto 6068502 Japan Univ Hyogo Kobe Hyogo 6512197 Japan Natl Inst Informat Tokyo 1018430 Japan

ISBN: (纸本)9783031157141;9783031157134

To mitigate the imbalance in the number of assignees in the Hospitals/Residents problem, Goko et al. [Goko et al., Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties, Proc. STAGS 2022, pp. 31:1-31:20] studied the Hospitals/Residents problem with lower quotas whose goal is to find a stable matching that satisfies lower quotas as much as possible. In their paper, preference lists are assumed to be complete, that is, the preference list of each resident (resp., hospital) is assumed to contain all the hospitals (resp., residents). In this paper, we study a more general model where preference lists may be incomplete. For four natural scenarios, we obtain maximum gaps of the best and worst solutions, approximability results, and inapproximability results.

关键词： Stable matching Hospitals/Residents problem Lower quota approximation algorithm Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Hardness and approximation Results of Roman {3}-Domination in Graphs 27th

Hardness and Approximation Results of Roman {3}-Domination i...

引用

27th International Computing and Combinatorics Conference (COCOON)

作者： Goyal, Pooja Panda, B. S. Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

ISBN: (纸本)9783030895433;9783030895426

A Roman {3}-dominating function (Double Italian dominating function) of a graph G = (V, E) is a function f : V -> {0, 1, 2, 3} having the property that for every vertex v is an element of V, if f(v) = 0, then Sigma(u is an element of N(v)) f(u) >= 3 and if f(v) = 1, then Sigma(u is an element of N(v)) f(u) >= 2. The weight, f(V), of a Roman {3}-dominating function f is Sigma(u is an element of V) f(u). The minimum weight of a Roman {3}-dominating function in a graph G is known as Roman {3}-domination number of G and is denoted by gamma({R3})(G). MINIMUM ROMAN {3}-DOMINATION problem is to find a Roman {3}- dominating function of minimum weight and DECIDE ROMAN {3}- DOMINATION is the decision version of MINIMUM ROMAN {3}-DOMINATION problem. DECIDE ROMAN {3}-DOMINATION is known to be NP-complete for bipartite graphs. In this paper, we show that DECIDE ROMAN {3}-DOMINATION is NP-complete for chordal graphs. We show that MINIMUM ROMAN {3}-DOMINATION problem is polynomial-time solvable for threshold graphs which is a subclass of chordal graphs. We propose an O(ln Delta(G)) approximation algorithm for MINIMUM ROMAN {3}-DOMINATION problem for a graph G with maximum degree Delta(G). Finally, we show that MINIMUM ROMAN {3}- DOMINATION problem is APX-complete for bounded degree graphs.

关键词： Roman {3}-Domination NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the maximum edge-pair embedding bipartite matching

引用

THEORETICAL COMPUTER SCIENCE 2021年 882卷 109-124页

作者： Nguyen, Cam Ly Suppakitpaisarn, Vorapong Surarerks, Athasit Vajanopath, Phanu Toshiba Co Ltd Tokyo Japan Univ Tokyo Tokyo Japan Chulalongkorn Univ Bangkok Thailand Kasetsart Univ Bangkok Thailand

Given a set of edge pairs in a complete bipartite graph, we want to find a bipartite matching that includes the maximum number of those edge pairs. While the problem has many applications to wireless localization and computer vision, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless P = N P, we show that there is no constant approximation for the problem. Then, we consider two special cases of the problem. Suppose that k denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, the first case is for when k is not large. While there is a simple polynomial-time algorithm for the problem when k is one, we show that the problem is NP-hard when k is greater than one. We also devise an efficient O(k)-approximation algorithm for the problem. For the second case, every pair of nodes in the same partition of the input bipartite graph are labeled with one of chi colors. We want to match, between the two partitions, a pair of nodes to a pair of nodes with the same color. Denote n as the number of nodes, we give an O (root chi(n))-approximation algorithm for this case. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Graph matching problem Wireless localization Computational complexity approximation algorithm Network optimization Quadratic assignment problem

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for Adaptive Seed Minimization 19

Efficient Approximation Algorithms for Adaptive Seed Minimiz...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Tang, Jing Huang, Keke Xiao, Xiaokui Lakshmanan, Laks V. S. Tang, Xueyan Sun, Aixin Lim, Andrew Natl Univ Singapore Dept Ind Syst Engn & Management Singapore Singapore Nanyang Technol Univ Sch Engn & Comp Sci Singapore Singapore Natl Univ Singapore Sch Comp Singapore Singapore Univ British Columbia Dept Comp Sci Vancouver BC Canada

ISBN: (纸本)9781450356435

As a dual problem of influence maximization, the seed minimization problem asks for the minimum number of seed nodes to influence a required number eta of users in a given social network G. Existing algorithms for seed minimization mostly consider the non-adaptive setting, where all seed nodes are selected in one batch without observing how they may influence other users. In this paper, we study seed minimization in the adaptive setting, where the seed nodes are selected in several batches, such that the choice of a batch may exploit information about the actual influence of the previous batches. We propose a novel algorithm, ASTI, which addresses the adaptive seed minimization problem in O (eta center dot(m+n)/epsilon(2) ln n) expected time and offers an approximation guarantee of (ln eta+1)(2)/(1-(1-1/b)(b))(1-1/e)(1-epsilon) in expectation, where eta is the targeted number of influenced nodes, b is size of each seed node batch, and epsilon is an element of (0, 1) is a user-specified parameter. To the best of our knowledge, ASTI is the first algorithm that provides such an approximation guarantee without incurring prohibitive computation overhead. With extensive experiments on a variety of datasets, we demonstrate the effectiveness and efficiency of ASTI over competing methods.

关键词： Seed Minimization Sampling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved approximations for Capacitated Vehicle Routing with Unsplittable Client Demands 1

引用

23rd International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Friggstad, Zachary Mousavi, Ramin Rahgoshay, Mirmahdi Salavatipour, Mohammad R. Univ Alberta Dept Comp Sci Edmonton AB Canada

ISBN: (数字)9783031069017

ISBN: (纸本)9783031069017;9783031069000

In this paper, we present improved approximation algorithms for the (unsplittable) Capacitated Vehicle Routing Problem (CVRP) in general metrics. In CVRP, introduced by Dantzig and Ramser (1959), we are given a set of points (clients) V together with a depot r in a metric space, with each v is an element of V having a demand d(v) > 0, and a vehicle of bounded capacity Q. The goal is to find a minimum cost collection of tours for the vehicle, each starting and ending at the depot, such that each client is visited at least once and the total demands of the clients in each tour is at most Q. In the unsplittable variant we study, the demand of a node must be served entirely by one tour. We present two approximation algorithms for unsplittable CVRP: a combinatorial (alpha + 1.75)-approximation, where alpha is the approximation factor for the Traveling Salesman Problem, and an approximation algorithm based on LP rounding with approximation guarantee alpha + ln(2) + delta approximate to 3.194 + delta in n(O(1/delta)) time. Both approximations can further be improved by a small amount when combined with recent work by Blauth, Traub, and Vygen (2021), who obtained an (alpha + 2 center dot (1 - epsilon))-approximation for unsplittable CVRP for some constant epsilon depending on alpha (epsilon > 1/3000 for alpha = 1.5).

关键词： Capacitated vehicle routing Combinatorial optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：