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

A fast approximate implementation of the work function algorithm for solving the -server problem

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2015年第3期23卷 699-722页

作者： Rudec, Tomislav Manger, Robert Univ Osijek Fac Elect Engn Osijek 31000 Croatia Univ Zagreb Dept Math Zagreb 10000 Croatia

In this paper we propose an approximate implementation of the work function algorithm (WFA) for solving the -server problem. Our implementation is based on network flow techniques, a novel network model, and flow cost reduction. Also, it is provided with a parameter that enables tradeoff between accuracy and speed. In the paper we present experiments, showing that the new implementation can mimic perfectly the original WFA and still run at least an order of magnitude faster than any known exact implementation.

关键词： Combinatorial optimization On-line computation k-server problem work function algorithm Implementation Network flows Cost reduction

来源：评论

学校读者我要写书评

暂无评论

THE GENERALIZED work function algorithm IS COMPETITIVE FOR THE GENERALIZED 2-SERVER PROBLEM

引用

SIAM JOURNAL ON COMPUTING 2014年第1期43卷 96-125页

作者： Sitters, Rene Vrije Univ Amsterdam Amsterdam Netherlands CWI Amsterdam Amsterdam Netherlands

The generalized 2-server problem is an online optimization problem where a sequence of requests has to be served at minimal cost. Requests arrive one by one and need to be served instantly by at least one of two servers. We consider the general model where the cost function of the two servers may be different. Formally, each server moves in its own metric space and a request consists of one point in each metric space. It is served by moving one of the two servers to its request point. Requests have to be served without knowledge of future requests. The objective is to minimize the total traveled distance. The special case where both servers move on the real line is known as the CNN problem. We show that the generalized work function algorithm, WFA lambda, is constant competitive for the generalized 2-server problem. Further, we give an outline for a possible extension to k >= 2 servers and discuss the applicability of our techniques and of the work function algorithm in general. We conclude with a discussion on several open problems in online optimization.

关键词： competitive analysis k-server problem online algorithms work function algorithm CNN problem metrical service system

来源：评论

学校读者我要写书评

暂无评论

A fast work function algorithm for solving the k-server problem

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2013年第1期21卷 187-205页

作者： Rudec, Tomislav Baumgartner, Alfonzo Manger, Robert Univ Zagreb Dept Math Zagreb 10000 Croatia Univ Osijek Fac Elect Engn Osijek 31000 Croatia

This paper deals with the work function algorithm (WFA) for solving the on-line k-server problem. The paper addresses some practical aspects of the WFA, such as its efficient implementation and its true quality of serving. First, an implementation of the WFA is proposed, which is based on network flows, and which reduces each step of the WFA to only one minimal-cost maximal flow problem instance. Next, it is explained how the proposed implementation can further be simplified if the involved metric space is finite. Also, it is described how actual computing of optimal flows can be speeded up by taking into account special properties of the involved networks. Some experiments based on the proposed implementation and improvements are presented, where actual serving costs of the WFA have been measured on very large problem instances and compared with costs of other algorithms. Finally, suitability of the WFA for solving real-life problems is discussed.

关键词： On-line problems On-line algorithms k-server problem work function algorithm Implementation Network flows

来源：评论

学校读者我要写书评

暂无评论

The K-server problem via a modern optimization lens

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第1期276卷 65-78页

作者： Bertsimas, Dimitris Jaillet, Patrick Korolko, Nikita MIT Ctr Operat Res Cambridge MA 02139 USA

We consider the well-known K-server problem from the perspective of mixed integer, robust and adaptive optimization. We propose a new tractable mixed integer linear formulation of the K-server problem that incorporates both information from the past and uncertainty about the future. By combining ideas from classical online algorithms developed in the computer science literature and robust and adaptive optimization developed in the operations research literature we propose a new method that (a) is computationally tractable, (b) almost always outperforms all other methods in numerical experiments, and (c) is stable with respect to potential errors in the assumptions about the future. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Scheduling Adaptive robust optimization work function algorithm

来源：评论

学校读者我要写书评

暂无评论

Online optimization with look-ahead for freeway emergency vehicle dispatching considering availability

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2019年 109卷 95-116页

作者： Park, Hyoshin Waddell, Deion Haghani, Ali North Carolina A&T State Univ Dept Computat Sci & Engn Greensboro NC 27401 USA Univ Maryland Dept Civil & Environm Engn College Pk MD 20742 USA

Traditional emergency management studies have made resource allocation decisions to serve the current emergency without knowing which future emergency will be occurring. Different ordered combinations of emergencies result in different performance outcomes. Even though future events can be anticipated, previous studies follow an assumption that events over a time interval are independent. This study follows an assumption that events are interdependent, because speed reduction and rubbernecking due to an initial incident provoke secondary incidents on freeways and the resource availability depends on service times of each request. The misconception that secondary incidents are not common has resulted in overlooking a look-ahead concept. This study is the pioneer in relaxing the structural assumptions of independency during the assignment of servers and approaching the challenge from an operational perspective, online optimization. The main objective is to minimize the time needed to respond to a sequence of requests. We introduce online dispatching strategies with visualization applied in different network sizes, number of requests, and service times to provide insights on model behavior and solution quality. The experimental evidence indicates that the algorithm works well in practice. We envision a new era in which an optimal resource allocation adapts to external events effectively and anticipates the future learning from the past to produce effective solutions.

关键词： Emergency response Online optimization Nearest neighbor algorithm work function algorithm Service time Secondary incidents

来源：评论

学校读者我要写书评

暂无评论

Empirical Analysis of algorithms for the k-Server and Online Bipartite Matching Problems

Empirical Analysis of Algorithms for the k-Server and Online...

引用

作者： Mahajan, Rutvij Sanjay Virginia Tech | University

The k–server problem is of significant importance to the theoretical computer science and the operations research community. In this problem, we are given k servers, their initial locations and a sequence of n requests that arrive one at a time. All these locations are points from some metric space and the cost of serving a request is given by the distance between the location of the request and the current location of the server selected to process the request. We must immediately process the request by moving a server to the request location. The objective in this problem is to minimize the total distance traveled by the servers to process all the requests. In this thesis, we present an empirical analysis of a new online algorithm for k-server problem. This algorithm maintains two solutions, online solution, and an approximately optimal offline solution. When a request arrives we update the offline solution and use this update to inform the online assignment. This algorithm is motivated by the Robust-Matching algorithm [RMalgorithm, Raghvendra, APPROX 2016] for the closely related online bipartite matching problem. We then give a comprehensive experimental analysis of this algorithm and also provide a graphical user interface which can be used to visualize execution instances of the algorithm. We also consider these problems under stochastic setting and implement a lookahead strategy on top of the new online algorithm.

关键词： k-Server Problem work function algorithm Bipartite Matching Assignment Problem Thesis

来源：评论

学校读者我要写书评

暂无评论

Asymptotically Optimal Online Page Migration on Three Points

引用

algorithmICA 2015年第4期71卷 1035-1064页

作者： Matsubayashi, Akira Kanazawa Univ Div Elect Engn & Comp Sci Kanazawa Ishikawa 9201192 Japan

This paper addresses the page migration problem: given online requests from nodes on a network for accessing a page stored in a node, output online migrations of the page. Serving a request costs the distance between the request and the page, and migrating the page costs the migration distance multiplied by the page size Da parts per thousand yen1. The objective is to minimize the total sum of service costs and migration costs. Black and Sleator conjectured that there exists a 3-competitive deterministic algorithm for every graph. Although the conjecture was disproved for the case D=1, whether or not an asymptotically (with respect to D) 3-competitive deterministic algorithm exists for every graph is still open. In fact, we did not know if there exists a 3-competitive deterministic algorithm for an extreme case of three nodes with Da parts per thousand yen2. As the first step toward an asymptotic version of the Black and Sleator conjecture, we present 3- and (3+1/D)-competitive algorithms on three nodes with D=2 and Da parts per thousand yen3, respectively, and a lower bound of 3+Omega(1/D) that is greater than 3 for every Da parts per thousand yen3. In addition to the results on three nodes, we also derive rho-competitiveness on complete graphs with edge-weights between 1 and 2-2/rho for any rho a parts per thousand yen3, extending the previous 3-competitive algorithm on uniform networks.

关键词： Page migration work function algorithm Competitive analysis Server problem

来源：评论

学校读者我要写书评

暂无评论

A new approach to solve the k-server problem based on network flows and flow cost reduction

引用

COMPUTERS & OPERATIONS RESEARCH 2013年第4期40卷 1004-1013页

作者： Rudec, Tomislav Manger, Robert Univ Osijek Fac Elect Engn Osijek 31000 Croatia Univ Zagreb Dept Math Zagreb 10000 Croatia

This paper is concerned with two algorithms for solving the k-server problem: the optimal off-line algorithm (OPT) and the on-line work function algorithm (WFA). Both algorithms are usually implemented by network flow techniques including the flow augmentation method. In the paper a new implementation approach is proposed, which is again based on network flows, but uses simpler networks and the cost reduction method. The paper describes in detail the corresponding new implementations of OPT and WFA, respectively. All necessary correctness proofs are given. Also, experiments are presented, which confirm that the new approach assures faster execution of both algorithms. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： On-line problems k-server problem Optimal off-line algorithm work function algorithm Implementation Network flows Cost reduction Experiments

来源：评论

学校读者我要写书评

暂无评论

Topology matters:: Smoothed competitiveness of metrical task systems

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期341卷 216-246页

作者： Schäfer, G Sivadasan, N Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Strand Genom Bangalore 560080 Karnataka India

Borodin et al. (J. ACM 39 (1992) 745) introduced metrical task systems, a framework to model a large class of online problems. Metrical task systems can be described as follows. We are given a graph G = (V, E) with n nodes and a positive edge length (e) for every edge e G E. An online algorithm resides in G and has to service a sequence of tasks that arrive online. A task r specifies for each node nu is an element of V a request cost r (nu) E R-0(+) boolean OR {infinity}. If the algorithm resides in node u before the arrival of task tau, the cost to service task tau in node nu is equal to the shortest path distance from u to v plus the request cost r(v). The objective is to service all tasks at minimum total cost. Borodin et al. showed that every deterministic online algorithm has a competitive ratio of at least 2n - 1, independent of the underlying metric. Moreover, they presented an online work function algorithm (WFA) that achieves this competitive ratio. We present a smoothed competitive analysis of WTA. That is, given an adversarial task sequence, we randomly perturb the request costs and analyze the competitive ratio of WFA on the perturbed sequence. Here, we are mainly interested in the asymptotic behavior of WFA. Our analysis reveals that the smoothed competitive ratio of WFA is much better than O(n) and that it depends on several topological parameters of the underlying graph G, such as the minimum edge length lambda(min), the maximum degree Delta, the edge diameter e(max), etc. For example, if the ratio between the maximum and the minimum edge length of G is bounded by a constant, the smoothed competitive ratio of WFA is O(e(max)(lambda(min)/sigma + log(Delta))) and O(root n (.) (lambda(min)/sigma + log(Delta))), where sigma denotes the standard deviation of the smoothing distribution. That is, already for perturbations with sigma = Theta(lambda(min)) the competitive ratio reduces to O(log(n)) on a clique and to O(root n) on a line. Furthermore, we provide

关键词： online algorithms competitive analysis smoothed analysis metrical task systems work function algorithm

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：