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

Latency-Bounded Off-Site Virtual Node Protection in NFV

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2021年第3期18卷 2545-2556页

作者： Peng, Chengzong Zheng, Danyang Philip, Sumesh Cao, Xiaojun Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Soochow Univ Sch Elect & Informat Engn Suzhou Key Lab Adv Opt Commun Network Technol Suzhou 215006 Peoples R China Illinois State Univ Sch Informat Technol Normal IL 61761 USA

In network function virtualization (NFV), the client's service requests will go through multiple service functions (SFs). The instances of the required SFs will be hosted on the geographically-distributed physical nodes in physical networks (PNs). The failure of any physical nodes or virtual nodes (i.e., SF instances) will impact the delivery of services and the client's experience. It is essential for service providers to take the node failure and network reliability into account. Different from physical node failures that will affect the PN's topology and connectivity, virtual node failures impact the services delivery of certain clients. As a result, applying traditional backup schemes that are designed for physical node failures may not efficiently provide protection for virtual node failures. In this work, we define and mathematically formulate a new latency-bounded off-site virtual node protection (LOVNP) problem in NFV. After proving the NP-hardness of the LOVNP problem, we introduce a novel shared protection technique called pairwise node protection to effectively facilitate the protection of node failures in NFV. Then, we propose an efficient heuristic algorithm called protection centrality based pairwise node protection (PC-PNP) to optimize the LOVNP problem and prove that PC-PNP has a logarithm-approximation boundary. Our extensive simulations and analysis show that the proposed algorithm significantly outperforms the algorithms that are extended from the existing work.

关键词： Reliability Network function virtualization Service function chaining Resource management approximation algorithms Servers Edge computing Network function virtualization network reliability reliable network design pairwise node protection approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for single vehicle scheduling on tree/cycle networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第3期42卷 565-580页

作者： Wu, Yuanxiao Lu, Xiwen East China Univ Sci & Technol Shanghai Peoples R China

The single vehicle scheduling problems based on tree/cycle networks are studied in this paper. Each customer, assumed as a vertex on the given network, has a release time and a service time requirement. The single vehicle starts from the depot and aims to serve all the customers. The objective of the problem is to find the optimal routing schedule so as to minimize the makespan. We provide a 169\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{16}{9}$$\end{document}-approximation algorithm and a 4825\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{48}{25}$$\end{document}-approximation algorithm for the tour-version and path-version of single vehicle scheduling problem on a tree, respectively. For the tour-version and path-version of single vehicle scheduling problem on a cycle, we present a 53\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{5}approximation algorithm$$\end{document}-approximation algorithm and a 2917\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{29}{17}$$\end{document}-approximation algorithm, respectively.

关键词： Vehicle Routing Scheduling Network approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

LOCAL SEARCH algorithm FOR THE SQUARED METRIC k-FACILITY LOCATION PROBLEM WITH LINEAR PENALTIES

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2021年第4期17卷 2013-2030页

作者： Wang, Yishui Zhang, Dongmei Zhang, Peng Zhang, Yong Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Shandong Jianzhu Univ Sch Software Jinan 250101 Peoples R China

In the k-facility location problem, an important combinatorial optimization problem combining the classical facility location and k-median problems, we are given the locations of some facilities and clients, and need to open at most k facilities and connect all clients to opened facilities, minimizing the facility opening and connection cost. This paper considers the squared metric k-facility location problem with linear penalties, a robust version of the k-facility location problem. In this problem, we do not have to connect all clients to facilities, but each client that is not served by any facility must pay a penalty cost. The connection costs of facilities and clients are supposed to be squared metric, which is more general than the metric case. We provide a constant approximation algorithm based on the local search scheme with add, drop, and swap operations for this problem. Furthermore, we improve the approximation ratio by using the scaling technique.

关键词： approximation algorithm local search k-facility location problem linear penalties squared metric

来源：评论

学校读者我要写书评

暂无评论

Delay Optimization for Wireless Powered Mobile Edge Computing with Computation Offloading via Deep Learning

引用

APPLIED SCIENCES-BASEL 2024年第16期14卷 7190页

作者： Lei, Ming Fu, Zhe Yu, Bocheng Shaanxi Normal Univ Sch Comp Sci & Technol Xian 710119 Peoples R China Xi An Jiao Tong Univ Dept Comp Sci & Technol Xian 710049 Peoples R China AVIC Xian Aeronaut Comp Tech Res Inst Xian 710068 Peoples R China

Mobile edge computing (MEC), specifically wireless powered mobile edge computing (WPMEC), can achieve superior real-time data analysis and intelligent processing. In WPMEC, different user nodes (UNs) harvest significantly different amounts of energy, which results in longer delays for lower-energy UNs when data are offloaded to MEC servers. This study involves quantifying the delays in energy harvesting and task offloading to edge servers in WPMEC via user cooperation. In this paper, a method for transferring the tasks that need to be offloaded to edge servers as quickly as possible is investigated. The problem is formulated as an optimization model to minimize the delay, including the time required for the energy harvesting and offloading tasks. Because the problem was non-deterministic polynomial hard (NP-hard), a delay-optimal approximation algorithm (DOPA) is proposed. Finally, with the training data generated based on the DOPA, a deep learning-based online offloading (DLOO) framework is designed for predicting the transmission power of each UN. After each UN's transmission power is obtained, the original model is converted to a linear programming problem, which substantially reduces the computational complexity of the DOPA for solving the mixed-integer linear programming problem, especially in large-scale networks. The numerical results show that compared with the non-cooperation methods for WPMEC, the proposed algorithm significantly reduces the total delay. Additionally, in the delay optimization process for a scale of six UNs, the average computation time of the DLOO is only 0.2% that of the DOPA.

关键词： WPMEC user cooperation deep learning approximation algorithm delay optimization

来源：评论

学校读者我要写书评

暂无评论

New algorithmic Solutions for Some Clustering and Network Design Problems

New Algorithmic Solutions for Some Clustering and Network De...

引用

作者： Guo, Xiangyu State University of New York at Buffalo

学位级别：Ph.D., Doctor of Philosophy

The thesis is formed by two parts, where we consider two prominent types of combinatorial optimization problem, namely clustering and network design problems. In the first part, we study clustering problems under various computation models inspired by modern data analysis tasks. Specifically, we study clustering tasks on distributed, dynamic, or online data input, with possible noise-tolerance requirement. These new computation models often incur extra problem dimensions, e.g. communication cost (in the distributed setting), or stability and response time (in the dynamic and online setting). We propose algorithms for several classical clustering problems under the aforementioned set- tings, including (noise-tolerant) k-center, k-means, k-median, and the closely-related facility location problem. The second part is devoted to degree-bounded network design problems. The degree constraints require the degree of each node being bounded by certain quantity, which often makes a network design problem much harder. We aim to design algorithms for several fundamental network design problems with degree constraints, including Group Steiner Tree (on Trees), Directed Steiner Tree, and Single-Commodity Buy-at-Bulk.

关键词： approximation algorithm Clustering Linear programming Network design Online algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Bounds for Stochastic Extensible Bin Packing Under Distributional Assumptions 7th

Improved Bounds for Stochastic Extensible Bin Packing Under ...

引用

7th International Symposium on Combinatorial Optimization (ISCO)

作者： Sagnol, Guillaume Waldschmidt, Daniel Schmidt Genannt Tech Univ Berlin Fak 2 Inst Math MA 5-2Str 17 Juni 136 D-10623 Berlin Germany

ISBN: (纸本)9783031185298;9783031185304

In the stochastic extensible bin packing problem, n items of random size must be packed into m bins of unit capacity. The number of bins is fixed, but their capacity can be extended at extra cost. This model plays an important role in surgery scheduling, where the extension of bin capacity represents overtime of operating rooms. It is known that this problem has a (1+ e(-1))-approximation algorithm in expectation for arbitrary probability distributions of the item sizes. Using the theory of second-order stochastic dominance, we obtain improved bounds when the sizes have a bounded Pietra or Gini index, and when they belong to specific parametric families, such as Gamma, Lognormal or Weibull distributions.

关键词： approximation algorithm Stochastic scheduling Extensible bin packing Second-order stochastic dominance

来源：评论

学校读者我要写书评

暂无评论

Local Search approximation algorithms for the Spherical k-Means Problem 13th

Local Search Approximation Algorithms for the Spherical k-Me...

引用

13th International Conference on algorithmic Aspects in Information and Management (AAIM)

作者： Zhang, Dongmei Cheng, Yukun Li, Min Wang, Yishui Xu, Dachuan Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Suzhou Univ Sci & Technol Suzhou Key Lab Big Data & Informat Serv Sch Business Suzhou 215009 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol 1068 Xueyuan Ave Shenzhen 518055 Peoples R China Beijing Univ Technol Dept Operat Res & Sci Comp Beijing 100124 Peoples R China

ISBN: (纸本)9783030271954;9783030271947

In this paper, we study the spherical k-means problem (SKMP) which is one of the most well-studied clustering problems. In the SKMP, we are given an n-client set D in d-dimensional unit sphere S-d, and an integer k <= n. The goal is to open a center subset F subset of S-d with vertical bar F vertical bar <= k that minimizes the sum of cosine dissimilarity measure for each client in D to the nearest open center. We give a (2(4 + root 7) + epsilon)-approximation algorithm for this problem using local search scheme.

关键词： Spherical k-means Local search approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

2-node-connectivity network design

引用

THEORETICAL COMPUTER SCIENCE 2024年 987卷

作者： Nutov, Zeev Open Univ Israel Raanana Israel

We consider 2-connectivity network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. center dot In the 1-CONNECTIVITY AUGMENTATION problem the goal is to augment a connected graph by a minimum size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural approximation ratio 2 for this problem, and also for the more general CROSSING FAMILY COVER problem. center dot In the 2-CONNECTED DOMINATING SET problem, we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm with expected approximation ratio ()(sigma(n) center dot log3 n), where sigma(n) = ()(logn center dot log log n center dot (log log log n)3). The unifying technique of both results is a reduction to the SUBSET STEINER CONNECTED DOMINATING SET problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.

关键词： 2-connectivity Dominating set approximation algorithm Symmetric crossing family

来源：评论

学校读者我要写书评

暂无评论

On scheduling multiple parallel two-stage flowshops with Johnson's Rule

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第2期47卷 12-12页

作者： Wu, Guangwei Zuo, Fu Shi, Feng Wang, Jianxin Cent South Univ Forestry & Technol Coll Comp & Informat Engn Changsha 410004 Peoples R China Cent South Univ Sch Comp Sci & Engn Changsha 410083 Peoples R China Xiangjiang Lab Changsha 410205 Peoples R China

It is well-known that the classical Johnson's Rule leads to optimal schedules on a two-stage flowshop. However, it is still unclear how Johnson's Rule would help in approximation algorithms for scheduling an arbitrary number of parallel two-stage flowshops with the objective of minimizing the makespan. Thus within the paper, we study the problem and propose a new efficient algorithm that incorporates Johnson's Rule applied on each individual flowshop with a carefully designed job assignment process to flowshops. The algorithm is successfully shown to have a runtime O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n \log n)$$\end{document} and an approximation ratio 7/3, where n is the number of jobs. Compared with the recent PTAS result for the problem (Dong et al. in Eur J Oper Res 218(1):16-24, 2020), our algorithm has a larger approximation ratio, but it is more efficient in practice from the perspective of runtime.

关键词： Scheduling Two-stage flowshop approximation algorithm Cloud computing

来源：评论

学校读者我要写书评

暂无评论

New algorithms for fair k-center problem with outliers and capacity constraints

引用

THEORETICAL COMPUTER SCIENCE 2024年 999卷

作者： Wu, Xiaoliang Feng, Qilong Xu, Jinhui Wang, Jianxin Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China Xiangjiang Lab Changsha Peoples R China SUNY Buffalo Dept Comp Sci & Engn New York NY USA Cent South Univ Hunan Prov Key Lab Bioinformat Changsha Peoples R China

The fair k-center problem has been paid lots of attention recently. In the fair k-center problem, we are given a set X of points in a metric space and a parameter k is an element of Z(+), where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k-center problem objective is minimized. In this paper, we consider the fair k-center problem with outliers and capacity constraints, denoted as the fair k-center with outliers (FkCO) problem and the capacitated fair k-center (CFkC) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + epsilon)-approximations with FPT time for the FkCO and CFkC problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the FkCO problem with some reasonable assumptions.

关键词： k-center Fairness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：