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

On-line load balancing in a hierarchical server topology

SIAM JOURNAL ON COMPUTING 2001年第2期31卷 527-549页

作者： Bar-Noy, A Freund, A Naor, JS AT&T Labs Res Shannon Lab Florham Pk NJ 07932 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

In a hierarchical server environment jobs are to be assigned in an on-line fashion to a collection of servers which form a hierarchy of capability: each job requests a specific server meeting its needs, but the system is free to assign it either to that server or to any other server higher in the hierarchy. Each job carries a certain load, which it imparts to the server it is assigned to. The goal is to nd a competitive assignment in which the maximum total load on a server is minimized. We consider the linear hierarchy in which the servers are totally ordered in terms of their capabilities. We investigate several variants of the problem. In the unweighted ( as opposed to weighted) problem all jobs have unit weight. In the fractional ( as opposed to integral) model a job may be assigned to several servers, each receiving some fraction of its weight. Finally, temporary ( as opposed to permanent) jobs may depart after being active for some finite duration of time. We show an optimal e-competitive algorithm for the unweighted integral permanent model. The same algorithm is (e+1)-competitive in the weighted case. Its fractional version is e-competitive even if temporary jobs are allowed. or the integral model with temporary jobs we show an algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case. We show a lower bound of e for the unweighted case ( both integral and fractional). This bound is valid even with respect to randomized algorithms. We also show a lower bound of 3 for the unweighted integral model when temporary jobs are allowed. We generalize the problem and consider hierarchies in which the servers form a tree. In the tree hierarchy, any job assignable to a node is also assignable to the node's ancestors. We show a deterministic algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case, where only permanent jobs are allowed. Randomizing this algorithm improves its competitiveness to e

关键词： on-line algorithms load balancing hierarchical servers temporary jobs resource procurement

来源：评论

学校读者我要写书评

暂无评论

A simpler competitive analysis for scheduling equal-length jobs on one machine with restarts

引用

INFORMATION PROCESSING LETTERS 2008年第6期107卷 240-245页

作者： Goldwasser, Michael H. Misra, Arundhati Bagchi St Louis Univ Dept Math & Comp Sci St Louis MO 63103 USA Mississippi State Univ Dept Math & Stat Mississippi State MS 39762 USA

We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadlines. Chrobak et al. (2007, SICOMP 36:6) introduce a preempt-restart model in which progress toward completing a preempted job is lost, yet that job can be restarted from scratch. They provide a 3/2-competitive deterministic algorithm and show that this is the optimal competitiveness. Their analysis is based on a complex charging scheme among individual jobs and the use of several partial functions and mappings for assigning the charges. In this paper, we provide an alternative proof of the result using a more global potential argument to compare the relative progress of the algorithm versus the optimal schedule over time. This new proof is significantly simpler and more intuitive that the original, and our technique is applicable to related problems. (C) 2008 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms on-line algorithms preemption scheduling

来源：评论

学校读者我要写书评

暂无评论

The generalized two-server problem

引用

JOURNAL OF THE ACM 2006年第3期53卷 437-458页

作者： Sitters, Rene A. Stougie, Leen Max Planck Inst Informat D-66123 Saarbrucken Germany Tech Univ Eindhoven NL-5600 MB Eindhoven Netherlands Ctr Wiskunde & Informat NL-1090 GB Amsterdam Netherlands

We consider the generalized on-line two-server problem in which each server moves in its own metric space. Requests for service arrive one-by-one and every request is represented by two points: one in each metric space. The problem is to move, at every request, one of the two servers to its request-point such that the total distance travelled by the two servers is minimized. The special case in which both metric spaces are the real line is known as the CNN-problem. It has been a well-known open question in on-line optimization if an algorithm with a constant-competitive ratio exists for this problem. We answer this question in the affirmative by providing a constant-competitive algorithm for the generalized two-server problem on any metric space. The basic result in this article is a characterization of competitiveness for metrical service systems that seems much easier to use when looking for a competitive algorithm. The existence of a competitive algorithm for the generalized two-server problem follows rather easily from this result.

关键词： algorithms theory work function metrical service system kappa-server problem on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling to minimize max flow time:: an optimal preemptive algorithm

引用

OPERATIONS RESEARCH LETTERS 2005年第6期33卷 597-602页

作者： Ambühl, C Mastrolilli, M IDSIA Ist Dalle Molle Intelligenza Artificiale CH-6928 Manno Switzerland

We investigate the maximum flow time minimization problem of on-line scheduling jobs on m identical parallel machines. When preemption is allowed, we derive an optimal algorithm with competitive ratio 2-1/m. When preemption is not allowed and m = 2, we show that the First In First Out heuristic achieves the best possible competitive ratio. (c) 2004 Elsevier B.V. All rights reserved.

关键词： scheduling preemption on-line algorithms max flow time

来源：评论

学校读者我要写书评

暂无评论

Offline file assignments for online load balancing

引用

INFORMATION PROCESSING LETTERS 2011年第4期111卷 178-183页

作者： Duetting, Paul Henzinger, Monika Weber, Ingmar Yahool Res Barcelona E-08003 Barcelona Spain Ecole Polytech Fed Lausanne Stn 14 CH-1015 Lausanne Switzerland Univ Vienna Fac Comp Sci A-1090 Vienna Austria

We study a novel load balancing problem that arises in web search engines. The problem is a combination of an offline assignment problem, where files need to be (copied and) assigned to machines, and an online load balancing problem, where requests ask for specific files and need to be assigned to a corresponding machine, whose load is increased by this. We present simple deterministic algorithms for this problem and exhibit an interesting trade-off between the available space to make file copies and the obtainable makespan. We also give non-trivial lower bounds for a large class of deterministic algorithms and present a randomized algorithm that beats these bounds with high probability. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Load balancing on-line algorithms Information retrieval File distribution

来源：评论

学校读者我要写书评

暂无评论

On-line routing of virtual circuits with applications to load balancing and machine scheduling

引用

JOURNAL OF THE ACM 1997年第3期44卷 486-504页

作者： Aspnes, J Azar, Y Fiat, A Plotkin, S Waarts, O TEL AVIV UNIV DEPT COMP SCIIL-69978 TEL AVIVISRAEL STANFORD UNIV DEPT COMP SCISTANFORDCA 94305 IBM CORP ALMADEN RES CTRLA JOLLACA

In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast) where the goal is to route all requests while minimizing the required bandwidth. We concentrate on the case of permanent virtual circuits (i.e., once a circuit is established, it exists forever), and describe an algorithm that achieves an O(log n) competitive ratio with respect to maximum congestion, where n is the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O(log n) factor. We also show that this result is tight, that is, for any on-line algorithm there exists a scenario in which Omega(log n) increase in bandwidth is necessary in directed networks. We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival. Assigning a job to a machine increases the machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load. For the related machines case, we describe the first algorithm that achieves constant competitive ratio. For the unrelated case (with n machines), we describe a new method that yields O(log n)-competitive algorithm. This stands in contrast to the natural greedy approach, whose competitive ratios is exactly n.

关键词： high-speed networks on-line algorithms optimization routing

来源：评论

学校读者我要写书评

暂无评论

On algorithm design for Metrical Task Systems

引用

ALGORITHMICA 1997年第4期18卷 461-485页

作者： Burley, WR Irani, S UNIV CALIF SAN DIEGO DEPT COMP SCI & ENGNLA JOLLACA 92093 UNIV CALIF IRVINE DEPT INFORMAT & COMP SCIIRVINECA 92717

We extend the definition of Metrical Task System, introduced by Borodin et al. in [4]. In the extended definition, a system is described by the underlying metric space of states M as well as a set of allowable tasks T. Any request to an algorithm must be a member of T. The extension makes the model powerful enough to characterize completely many important on-line problems. We consider methods of designing competitive algorithms given the description of a system (M, I). In particular, we show that it is PSPACE-hard to determine the behavior of a c(M, I)-competitive algorithm, where c(M, I) is the best possible competitive ratio on (M, I). In addition, we show a simple, polynomial-rime algorithm for task systems [U-n, I] (where U-n is the uniform metric space on n nodes) that achieves a competitive ratio of O(log n . C(M, T)).

关键词： analysis of algorithms on-line algorithms competitive analysis approximation algorithms PSPACE-completeness metrical task systems

来源：评论

学校读者我要写书评

暂无评论

Universal algorithms for learning theory part I : piecewise constant functions

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2005年第9期6卷 1297-1321页

作者： Binev, P Cohen, A Dahmen, W DeVore, R Temlyakov, V Univ S Carolina Dept Math Ind Math Inst Columbia SC 29208 USA Univ Paris 06 Lab Jacques Louis Lions F-75013 Paris France Rhein Westfal TH Aachen Inst Geomet & Prakt Math D-52056 Aachen Germany

This paper is concerned with the construction and analysis of a universal estimator for the regression problem in supervised learning. Universal means that the estimator does not depend on any a priori assumptions about the regression function to be estimated. The universal estimator studied in this paper consists of a least-square fitting procedure using piecewise constant functions on a partition which depends adaptively on the data. The partition is generated by a splitting procedure which differs from those used in CART algorithms. It is proven that this estimator performs at the optimal convergence rate for a wide class of priors on the regression function. Namely, as will be made precise in the text, if the regression function is in any one of a certain class of approximation spaces (or smoothness spaces of order not exceeding one - a limitation resulting because the estimator uses piecewise constants) measured relative to the marginal measure, then the estimator converges to the regression function (in the least squares sense) with an optimal rate of convergence in terms of the number of samples. The estimator is also numerically feasible and can be implemented on-line.

关键词： distribution-free learning theory nonparametric regression universal algorithms adaptive approximation on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic TCP acknowledgment in the LogP model

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2003年第2期48卷 407-428页

作者： Frederiksen, JS Larsen, KS Noga, J Uthaisombut, P Univ So Denmark Dept Math & Comp Sci Odense Denmark Calif State Univ Northridge Dept Comp Sci Northridge CA 91330 USA Univ Pittsburgh Dept Comp Sci Pittsburgh PA 15260 USA

When messages, which are to be sent point-to-point in a network, become available at irregular intervals, a decision must be made each time a new message becomes available as to whether it should be sent immediately or if it is better to wait for more messages and send them all together. Because of physical properties of the networks, a certain minimum amount of time must elapse in between the transmission of two packets. Thus, whereas waiting delays the transmission of the current data, sending immediately may delay the transmission of the next data to become available even more. We propose a new quality measure and derive optimal deterministic and randomized algorithms for this on-line problem. (C) 2003 Elsevier Inc. All rights reserved.

关键词： dynamic TCP acknowledgment packet bundling on-line algorithms competitive ratio flow-time deterministic randomized

来源：评论

学校读者我要写书评

暂无评论

LRU is better than FIFO

引用

ALGORITHMICA 1999年第2期23卷 180-185页

作者： Chrobak, M Noga, J Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Univ Calif Riverside Dept Math Riverside CA 92521 USA

In the paging problem we have to manage a two-level memory system, in which the first level has short access time but can hold only up to k pages, while the second level is very large but slow. We use competitive analysis to study the relative performance of the two best known algorithms for paging, LRU and FIFO. Sleator and Tarjan proved that the competitive ratio of LRU and FIFO is k. In practice, however, LRU is known to perform much better than FIFO. It is believed that the superiority of LRU can be attributed to locality of reference exhibited in request sequences. In order to study this phenomenon, Borodin et al. [2] refined the competitive approach by introducing the concept of access graphs. They conjectured that the competitive ratio of LRU on each access graph is less than or equal to the competitive ratio of FIFO. We prove this conjecture in this paper.

关键词： paging caching on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：