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

NORA: An Approach for Transforming Network Management Policies into Automated Planning Problems

SENSORS 2021年第5期21卷 1790-1790页

作者： Rodriguez-Vivas, Angela Caicedo, Oscar Mauricio Ordonez, Armando Nobre, Jeferson Campos Granville, Lisandro Zambenedetti Univ Cauca Dept Telemat Popayan 190002 Colombia Univ Fed Rio Grande do Sul Inst Informat BR-90040060 Porto Alegre RS Brazil

Realizing autonomic management control loops is pivotal for achieving self-driving networks. Some studies have recently evidence the feasibility of using Automated Planning (AP) to carry out these loops. However, in practice, the use of AP is complicated since network administrators, who are non-experts in Artificial Intelligence, need to define network management policies as AP-goals and combine them with the network status and network management tasks to obtain AP-problems. AP planners use these problems to build up autonomic solutions formed by primitive tasks that modify the initial network state to achieve management goals. Although recent approaches have investigated transforming network management policies expressed in specific languages into low-level configuration rules, transforming these policies expressed in natural language into AP-goals and, subsequently, build up AP-based autonomic management loops remains unexplored. This paper introduces a novel approach, called NORA, to automatically generate AP-problems by translating Goal Policies expressed in natural language into AP-goals and combining them with both the network status and the network management tasks. NORA uses Natural Language Processing as the translation technique and templates as the combination technique to avoid network administrators to learn policy languages or AP-notations. We used a dataset containing Goal Policies to evaluate the NORA's prototype. The results show that NORA achieves high precision and spends a short-time on generating AP-problems, which evinces NORA aids to overcome barriers to using AP in autonomic network management scenarios.

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Q-SR: An extensible optimization framework for segment routing

引用

COMPUTER NETWORKS 2021年 200卷 108517-108517页

作者： Zhang, Jianwei Zhao, Chenwei Zhejiang Univ City Coll Sch Comp & Comp Sci 51 Huzhou St Hangzhou 310015 Zhejiang Peoples R China Zhejiang Univ Coll Comp Sci & Technol 38 Zheda Rd Hangzhou 310027 Zhejiang Peoples R China

Segment routing (SR) combines the advantages of source routing powered by software-defined networking (SDN) paradigm and hop-by-hop routing in legacy network infrastructure. The recent applications of SR in multi-domain network and service function chaining (SFC) entail the efficient use of multiple segments. However, because of the computation inefficiency, it is nearly impossible to accurately evaluate whether and to what extent various types of networks will benefit from SR with multiple segments using conventional approaches. In this paper, we propose a flexible Q-SR framework as well as its formulation in order to fully explore the potential of SR from an algorithmic perspective. The framework is highly extensible to design and evaluate algorithms that can be adapted to various network topologies and traffic matrices. For the offline setting, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1 +w) approximation solution for any specified w > 0 in time that is a polynomial function of the network size. To the best of our knowledge, the proposed FPTAS is the first algorithm that can compute arbitrarily accurate solution. For the online setting, we develop an online primal-dual algorithm that is proven to be O(1)-competitive and violates link capacities by a factor of O(logn), where n is the node number of the network. For the proposed approximation algorithms, we prove theoretical performance bounds and conduct extensive simulations on synthetic and realistic networks to analyze SR related and algorithmic parameters and validate the computation efficiency in both offline and online scenarios.

关键词： Segment routing (SR) Traffic engineering (TE) approximation algorithm Online algorithm Software-defined networking (SDN)

来源：评论

学校读者我要写书评

暂无评论

Recommending Deployment Strategies for Collaborative Tasks 20

Recommending Deployment Strategies for Collaborative Tasks

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Wei, Dong Roy, Senjuti Basu Amer-Yahia, Sihem NJIT Newark NJ 07102 USA Univ Grenoble Alpes CNRS Grenoble France

ISBN: (纸本)9781450367356

Our work contributes to aiding requesters in deploying collaborative tasks in crowdsourcing. We initiate the study of recommending deployment strategies for collaborative tasks to requesters that are consistent with deployment parameters they desire: a lower-bound on the quality of the crowd contribution, an upper-bound on the latency of task completion, and an upper-bound on the cost incurred by paying workers. A deployment strategy is a choice of value for three dimensions: Structure (whether to solicit the workforce sequentially or simultaneously), Organization (to organize it collaboratively or independently), and Style (to rely solely on the crowd or to combine it with machine algorithms). We propose StratRec, an optimization-driven middle layer that recommends deployment strategies and alternative deployment parameters to requesters by accounting for worker availability. Our solutions are grounded in discrete optimization and computational geometry techniques that produce results with theoretical guarantees. We present extensive experiments on Amazon Mechanical Turk, and conduct synthetic experiments to validate the qualitative and scalability aspects of StratRec.

关键词： deployment strategy recommendation approximation algorithm computational geometry crowdsourcing

来源：评论

学校读者我要写书评

暂无评论

Minimizing total job completion time in MapReduce scheduling

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2021年 158卷 107387-107387页

作者： Dong, Jianming Goebel, Randy Hu, Jueliang Lin, Guohui Su, Bing Zhejiang Sci Tech Univ Dept Math Hangzhou Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Xian Technol Univ Sch Econ & Management Xian Peoples R China

We follow up an earlier studied multiple-task parallel-machine scheduling model that captures the core challenges in MapReduce scheduling, with the optimization goal to minimize the total job completion time. The problem is a novel generalization of the classic two-stage flow-shop scheduling, in which we are given a set of jobs each is associated with multiple map tasks and multiple reduce tasks. All these tasks are non-preemptive to be processed on multiple parallel identical map machines and multiple parallel identical reduce machines, respectively, under the strict precedence constraints that, for each job, any reduce task cannot start before all its map tasks have been finished. We prove a new lower bound on the total job completion time, and based on which we present an O(nlogn + N + m(1) + m(2))-time (9-3/m(1))-approximation algorithm, where n and N are the number of jobs and the total number of tasks, respectively, m(1) and m(2) are the numbers of map and reduce machines, respectively, and they can even be part of the input. Our algorithm improves the previous best 12-approximation, and it reduces to the best approximation algorithms for several interesting or well studied special cases. We confirm through numerical experiments on 828, 100 instances that both our lower bound and our algorithm significantly outperform: the empirical mean improvement ratio of the new lower bound is as high as 37.75%, and the empirical mean approximation ratio of our algorithm is only 1.7582.

关键词： MapReduce scheduling Two-stage flow-shop Parallel identical machines Shortest processing time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Two competitive agents to minimize the weighted total late work and the total completion time

引用

APPLIED MATHEMATICS AND COMPUTATION 2021年 406卷 126286-126286页

作者： Zhang, Xingong Chongqing Normal Univ Coll Math Sci Chongqing 401331 Peoples R China

This paper studies deterministic constraint optimization problem with two competitive agents in which the following objective functions on a single machine: the total weighted late work and the total completion time. We show that the constraint optimization problem is the binary NP-hard by Knapsack problem reduction. Furthermore, we present a pseudo-polynomial time algorithm by early due date maximum not-late sequence, and an approximation Pareto curve by dynamic programming algorithm and two eliminated states, which time complexity of the two approximation algorithms are O(n(A)(2)n(B)Q Sigma (p(j)(A) + p(j)(B))) and O(n(4)/theta(2) log UBA log UBB), where p(j), theta are processing time of job J(j), a given positive constant, and UBx an upper bound of the objective function of agent x, x subset of {A, B}. Finally, we present a simple approximation algorithm by the earliest due date (EDD) rule, which jobs of agent B are assigned an dummy due date. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Two competitive agent Single-machine scheduling Total late work approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Parallel Machine Scheduling Problem Maximizing Total Weighted Early Work

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2021年第6期38卷 2150007-2150007页

作者： Choi, Byung-Cheon Park, Myoung-Ju Kim, Kyung Min Min, Yunhong Chungnam Natl Univ Sch Business 99 Daehak Ro Daejeon 34134 South Korea Kyung Hee Univ Dept Ind & Management Syst Engn 1732 Deogyeong Daero Yongin 17104 Kyunggi Do South Korea Myongji Univ Dept Ind Management & Engn 116 Myongji Ro Yongin 17058 Gyeonggi Do South Korea Incheon Natl Univ Grad Sch Logist 119 Acad Ro Incheon 22012 Gyeonggi Do South Korea

We consider the total weighted early work maximization problem on identical machines in parallel such that the weights are identical, or the due date is the same. First, we present an approach to solve the case with a fixed number of machines in pseudo-polynomial time. Then, we develop approximation algorithms for the two cases with identical weights and with a common due date. For the case with identical weights, furthermore, we show that the parallel-machine and a single-machine cases are strongly NP-hard and weakly NP-hard, respectively, even if the due date of each job is equal to the processing time multiplied by a constant.

关键词： Scheduling early work computational complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Budgeted Data Caching based on k-Median in Mobile Edge Computing 13

Budgeted Data Caching based on k-Median in Mobile Edge Compu...

引用

13th IEEE International Conference on Services Computing (SCC) / 13th IEEE International Conference on Web Services (ICWS)

作者： Xia, Xiaoyu Chen, Feifei Cui, Guangming Abdelrazek, Mohamed Grundy, John Jin, Hai He, Qiang Deakin Univ Sch Informat Technol Geelong Vic Australia Swinburne Univ Technol Sch Software & Elect Engn Hawthorn Vic Australia Monash Univ Fac Informat Technol Clayton Vic Australia Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan Hubei Peoples R China Chengdu Univ Informat Technol Sch Software Engn Chengdu Sichuan Peoples R China

ISBN: (纸本)9781728187860

In mobile edge computing (MEC), edge servers are deployed at base stations to provide highly accessible computational resources and storage capacities to nearby mobile devices. Caching data on edge servers can ensure the service quality and network latency for those mobile devices. However, an app vendor needs to ensure that the data caching cost does not exceed its data caching budget. In this paper, we present the budgeted edge data caching (BEDC) problem as a constrained optimization problem to maximize the overall reduction in data retrieval for all its app users within the budget, and prove that it is NP-hard. Then, we provide an approach named IP-BEDC for solving the BEDC problem optimally based on Integer Programming. We also provide an O(k)-approximation algorithm, namely alpha-BEDC, to find near-optimal solutions to the BEDC problems efficiently. Our proposed approaches are evaluated on a real-world data set and a synthesized data set. The results demonstrate that our approaches can solve the BEDC problem effectively and efficiently while significantly outperforming five representative approaches.

关键词： mobile edge computing data caching low-latency services optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Non-Submodular Maximization with Matroid and Knapsack Constraints

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2021年第5期38卷 2140001-2140001页

作者： Wang, Yijing Du, Donglei Jiang, Yanjun Zhang, Xianzhao Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada Ludong Univ Sch Math & Stat Sci Yantai 264025 Peoples R China Linyi Univ Sch Math & Stat Linyi 276005 Shandong Peoples R China

We investigate the problem of maximizing a gamma-submodular function subject to one or multiple matroid constraints and one knapsack constraint. By the greedy local search technique, we present approximation algorithms with constant approximation ratios. When gamma = 1, our model reduces to the regular submodular maximization problem investigated in the literature under the same type of constraints. Our results therefore contribute towards the line of research on constrained non-submodular function maximization.

关键词： Non-submodular maximization matroid knapsack approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：