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

An optimal randomized online algorithm for the -Canadian Traveller Problem on node-disjoint paths

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第1期30卷 87-96页

作者： Bender, Marco Westphal, Stephan Univ Gottingen Inst Numer & Appl Math D-37073 Gottingen Germany

We consider the -Canadian Traveller Problem, which asks for a shortest path between two nodes and in an undirected graph, where up to edges may be blocked. An online algorithm learns about a blocked edge when reaching one of its endpoints. Recently, it has been shown that no randomized online algorithm can be better than -competitive, even if all --paths are node-disjoint. We show that the bound is tight by constructing a randomized online algorithm for this case that achieves the ratio against an oblivious adversary and is therefore best possible.

关键词： Competitive analysis online algorithm Canadian Traveller Problem

来源：评论

学校读者我要写书评

暂无评论

An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times

引用

OPTIMIZATION LETTERS 2010年第2期4卷 227-237页

作者： Liu, Ming Chu, Chengbin Xu, Yinfeng Zheng, Feifeng Ecole Cent Paris Lab Genie Ind F-92295 Chatenay Malabry France Xi An Jiao Tong Univ Sch Management Xian 710049 Shaanxi Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Shaanxi Peoples R China

This paper deals with a two-machine open shop scheduling problem. The objective is to minimize the makespan. Jobs arrive over time. We study preemption-resume model, i.e., the currently processed job may be preempted at any moment in necessary and be resumed some time later. Let p(1, j) and p(2, j) denote the processing time of a job J(j) on the two machines M-1 and M-2, respectively. Bounded processing times mean that 1 <= p(i, j) <= alpha (i = 1, 2) for each job J(j), where alpha >= 1 is a constant number. We propose an optimal online algorithm with a competitive ratio 5 alpha-1/4 alpha.

关键词： Open shop scheduling Bounded processing times Competitive analysis online algorithm

来源：评论

学校读者我要写书评

暂无评论

An Optimal online algorithm for Halfplane Intersection

引用

Journal of Computer Science & Technology 2000年第3期15卷 295-299页

作者：武继刚计永昶陈国良 DepartmentofComputerScience YantaiUniversityYantai264005P.R.China

The intersection of N half Planes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). ln this paper, an optimal online algorithm which runs also in time O(N log N) for this problem is presented. The main idea of the algorithm is to give a new definition for the left side of a given line, to assign the order for the points of a convex polygon, and then to use binary search method in an ordered vertex *** data structure used in the algorithm is no more complex than array.

关键词： computational geometry intersection of halfplanes online algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

An online algorithm for Virtualized Network Function Placement in Mobile Edge Industrial Internet of Things

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2023年第3期19卷 2496-2507页

作者： Liang, Junbin Tian, Fengsen Guangxi Univ Sch Comp Elect & Informat Guangxi Key Lab Multimedia Commun & Network Techno Nanning 530004 Peoples R China

Mobile edge Industrial Internet of Things (MEIIoT) is composed of Industrial Internet of Things (IIoT) and mobile edge computing, which is currently a new type of IIoT. MEIIoT has the characteristics of large scale and strong dynamics (e.g., network topology or number of IIoT devices would change from time to time). The placement of virtualized network functions (VNFs) in MEIIoT refers to placing multiple network functions (e.g., motion analyzer and video processor) on edge nodes in a form of software instances, so that IIoT devices can flexibly obtain services of these VNFs. However, an edge node can only be placed a small number of VNFs, because of its limited storage and computing resources. Therefore, if an IIoT device requires multiple VNFs, it needs to transmit its data to access several edge nodes, which would cause high delay. How to optimally place all the VNFs on edge nodes in MEIIoT, so that the whole access delay for all IIoT devices that requiring VNFs is minimized, is a challenging problem. In this article, we design an online placement algorithm. First, we decompose a long-term VNFs optimization problem into a series of one-shot optimization problems. Second, we formulate these one-shot problems into integer nonlinear programming problems, and prove that they are NP-hard. To overcome this hardness, we then propose a heuristic algorithm. Finally, we carried out extensive experiments with real-world datasets to validate the efficacy of our proposed solution.

关键词： Industrial Internet of Things Heuristic algorithms Delays Monitoring Informatics Vehicle dynamics Routing Mobile edge Industrial Internet of Things (IIoT) online algorithm virtualized network functions (VNFs) VNFs placement

来源：评论

学校读者我要写书评

暂无评论

Probability-Based online algorithm for Switch Operation of Energy Efficient Data Center

引用

IEEE TRANSACTIONS ON CLOUD COMPUTING 2022年第1期10卷 608-618页

作者： Sun, Jun Yang, Qinmin Yang, Zaiyue Zhejiang Univ Coll Control Sci & Engn State Key Lab Ind Control Technol Hangzhou 310027 Peoples R China Southern Univ Sci & Technol Dept Mech & Energy Engn Shenzhen 518055 Peoples R China

The huge amount of energy consumed by the data centers around the world every year motivates the cloud service providers to operate data centers in a more energy efficient way. A promising solution is to turn off the idle servers, which, however, may be turned on later, incurring a significant startup cost. The problem turns to dynamically provisioning the workload, and cutting down the energy cost which includes the power to support the running of data center and the startup cost. Different from previous studies that usually consider the worst-case performance guarantee when designing online algorithms, this paper considers the average case which is more practical. We propose a simple online algorithm based on the expectation of job interval of workload, which is proven to be optimal for exponential and uniform distributions and achieves tight competitive ratio e/e-1 and 4/3, respectively, for them. Simulations using the synthetic data verify our theoretical analysis. Numerical results employing Google's data center workload trace demonstrate that the proposed algorithm outperforms the worst case-based algorithm in terms of operation cost reduction.

关键词： Data center operation energy efficient startup cost online algorithm probability based analysis

来源：评论

学校读者我要写书评

暂无评论

A primal-dual online algorithm for the κ-server problem on weighted HSTs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第4期34卷 1133-1146页

作者： Chen, Wenbin Li, Fufang Wang, Jianxiong Qi, Ke Tang, Maobin Wang, Xiuni Guangzhou Univ Dept Comp Sci Guangzhou Guangdong Peoples R China Guangzhou Univ Guangdong Prov Engn Technol Res Ctr Math Educ Sof Guangzhou Guangdong Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China

In this paper, we show that there is a 5/2 l .ln(1+ kappa)-competitive randomized algorithm for the kappa-sever problem on weighted Hierarchically Separated Trees (HSTs) with depth l when n = kappa + 1 where n is the number of points in the metric space, which improved previous best competitive ratio 12l ln(1 + 4l (1 + k)) by Bansal et al. (FOCS, pp 267-276, 2011).

关键词： kappa-server problem online algorithm Primal-dual method Randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

An Efficient online algorithm for Dynamic SDN Controller Assignment in Data Center Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2017年第5期25卷 2788-2801页

作者： Wang, Tao Liu, Fangming Xu, Hong Huazhong Univ Sci & Technol Sch Comp Sci & Technol Serv Comp Technol & Syst Lab Cluster & Grid Comp Lab Wuhan 430074 Hubei Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

Software defined networking is increasingly prevalent in data center networks for it enables centralized network configuration and management. However, since switches are statically assigned to controllers and controllers are statically provisioned, traffic dynamics may cause long response time and incur high maintenance cost. To address these issues, we formulate the dynamic controller assignment problem (DCAP) as an online optimization to minimize the total cost caused by response time and maintenance on the cluster of controllers. By applying the randomized fixed horizon control framework, we decompose DCAP into a series of stable matching problems with transfers, guaranteeing a small loss in competitive ratio. Since the matching problem is NP-hard, we propose a hierarchical two-phase algorithm that integrates key concepts from both matching theory and coalitional games to solve it efficiently. Theoretical analysis proves that our algorithm converges to a near-optimal Nash stable solution within tens of iterations. Extensive simulations show that our online approach reduces total cost by about 46%, and achieves better load balancing among controllers compared with static assignment.

关键词： Software defined networking data center network online algorithm stable matching coalitional game

来源：评论

学校读者我要写书评

暂无评论

An online algorithm for VNF Service Chain Scaling in Datacenters

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2020年第3期28卷 1061-1073页

作者： Luo, Ziyue Wu, Chuan Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

Built on top of virtualization technologies, network function virtualization (NFV) provides flexible and scalable software implementation of various network functions. Virtual network functions (VNFs), which are network functions implemented as virtual machines, are chained together to provide network services. Dynamic deployment of VNFs while satisfying incoming network traffic demand is the key to cost optimization of an NFV system. Besides considering server resource capacity and incoming traffic rates, an optimal scaling policy needs to strike a balance between VNF's operational costs, the costs for maintaining VNF instances, and VNF deployment costs, additional costs when setting up new VNF instances on a server. This paper targets dynamic scaling of VNF instances in a cloud data center where multiple VNF chains are running. We propose an online scaling algorithm to adjust the deployment of VNF instances according to time-varying traffic demand, ensuring a good competitive ratio. Through theoretical analysis and trace-driven simulation, we demonstrate effectiveness of the proposed online VNF scaling algorithm.

关键词： Servers Heuristic algorithms Cloud computing Optimization Middleboxes Prediction algorithms IEEE transactions Network function virtualization service chains online algorithm dynamic scaling

来源：评论

学校读者我要写书评

暂无评论

Stochastic Dynamic Programming-Based online algorithm for Energy Management of Integrated Energy Buildings With Electric Vehicles and Flexible Thermal Loads

引用

IEEE ACCESS 2021年 9卷 58780-58789页

作者： Cheng, Renli Cheng, Weijie Li, Jie Chen, Zeqi Shi, Jun Pan, Zhenning Wu, Yufeng Yu, Tao Shenzhen Power Supply Bur Co Ltd Shenzhen 518000 Peoples R China South China Univ Technol Coll Elect Power Guangzhou 510640 Peoples R China

With the rapid development of economy and technology, large-scale integrated energy buildings account for an increasing proportion of urban load. However, the randomness of EV owner behaviors, electricity price and outdoor temperature have brought challenges to the energy management of integrated energy buildings. This paper proposes a stochastic dynamic programming-based online algorithm to address the energy management of integrated energy buildings with electric vehicles and flexible thermal loads under multivariate uncertainties. First, an online energy management framework is established, which is further formulated as a multi-stage stochastic sequential decision-making problem. To address the complexities of the problem, a novel stochastic dynamic programming is employed to develop a distribution-free, computationally efficient, and scalable solution. By using extensive training samples, the algorithm is trained offline to learn how to deal with multivariate uncertainties and get the approximate optimal solution, which no longer depends on intraday forecast information. Numerical tests demonstrate the effectiveness of the proposed algorithm compared with other online algorithms in terms of optimality and computation efficiency.

关键词： Buildings Resistance heating Uncertainty Heuristic algorithms Energy management Water heating Stochastic processes Stochastic dynamic programming online algorithm energy management integrated energy building multivariate uncertainties

来源：评论

学校读者我要写书评

暂无评论

A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

引用

JOURNAL OF SCHEDULING 2011年第4期14卷 361-369页

作者： Yuan, Jinjiang Fu, Ruyan Ng, C. T. Cheng, T. C. E. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China China Univ Min & Technol Sch Sci Xuzhou 221116 Jiangsu Peoples R China

We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5 - root 5)/2. We give an online algorithm for the considered problem with a competitive ratio (5 - root 5)/2 approximate to 1.382.

关键词： Parallel-batch scheduling online algorithm Restart Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：