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

Competitive deadline scheduling via additional or faster processors

JOURNAL OF SCHEDULING 2003年第2期6卷 213-223页

作者： Koo, CY Lam, TW Ngan, TW To, KK Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

This paper studies on-line scheduling in a single-processor system that allows preemption. The aim is to maximize the total value of jobs completed by their deadlines. It is known that if the on-line scheduler is given a processor faster (say, two times faster) than the off-line scheduler, then there exists an on-line algorithm called SLACKER that can achieve an O(1) competitive ratio. In this paper, we show that using additional unit-speed processors instead of a faster processor is a possible but not cost effective way to achieve an O(1) competitive ratio. Specifically, we find that-Theta(log k) unit-speed processors are required, where k is the importance ratio. Another contribution of this paper is an improved analysis of the competitiveness of SLACKER;this new analysis enables us to show that SLACKER, when extended to multi-processor systems, can still guarantee an O(1) competitive ratio.

关键词： on-line algorithms extra-resource analysis competitiveness deadline scheduling

来源：评论

学校读者我要写书评

暂无评论

On-line restricted assignment of temporary tasks with unknown durations

引用

INFORMATION PROCESSING LETTERS 2003年第2期85卷 67-72页

作者： Armon, A Azar, Y Epstein, L Regev, O Interdisciplinary Ctr Sch Comp Sci Herzliyya Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Inst Adv Study Princeton NJ 08540 USA

We consider load balancing of temporary tasks on m machines in the restricted assignment model. It is known that the best competitive ratio for this problem is Theta(rootm). This bound is not achieved by the greedy algorithm whose competitive ratio is known to be Omega(m(2/3)). We give an alternative analysis to the greedy algorithm which is better than the known analysis for relatively small values of m. We also show that for a small number of machines, namely m less than or equal to 5, the greedy algorithm is optimal. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms competitiveness temporary tasks

来源：评论

学校读者我要写书评

暂无评论

Dynamic schemes for speculative execution of code

引用

PERFORMANCE EVALUATION 2003年第2期53卷 125-142页

作者： Raghavan, P Shachnai, H Yaniv, M Ver Inc Sunnyvale CA 94089 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

Speculative execution of code is becoming a key technique for enhancing the performance of pipeline processors. In this work we study schemes that predict the execution path of a program based on the history of branch executions. Building on previous work, we present a model for analyzing the effective speedup from pipelining, when speculative execution is employed. We follow this with stochastic analyses of several schemes for speculative execution. A main result of our study is that if we can predict branch resolution with high probability (as in the Pentium Pro processor, e.g.) the Single Path scheme commonly used on modem processors is within factor of 2 from the optimal. We conclude with simulations covering several of the settings that we study. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： pipeline processors speculative execution branch prediction on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Competitive on-line switching policies

引用

ALGORITHMICA 2003年第3期36卷 225-247页

作者： Bar-Noy, A Freund, A Landa, S Naor, J CUNY Brooklyn Coll Dept Comp & Informat Sci Brooklyn NY 11210 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel AT&T Labs Res Shannon Lab Florham Pk NJ 07932 USA

Consider the following problem. A switch connecting n input channels to a single output channel must deliver all incoming messages through this channel. Messages are composed of packets, and in each time slot the switch can deliver a single packet from one of the input queues to the output channel. In order to prevent packet loss, a buffer is maintained for each input channel. The goal of a switching policy is to minimize the maximum buffer size. The setting is on-line;decisions must be made based on the current state without knowledge of future events. This general scenario models multiplexing tasks in various systems such as communication networks, cable modem systems, and traffic control. Traditionally, researchers analyzed the performance of a given policy assuming some distribution on the arrival rates of messages at the input queues, or assuming that the service rate is at least the aggregate of all the input rates. We use competitive analysis, avoiding any prior assumptions on the input. We show O(log n)-competitive switching policies for the problem and demonstrate matching lower bounds.

关键词： on-line algorithms packet switching

来源：评论

学校读者我要写书评

暂无评论

An experimental study of on-line methods for zone construction in arrangements of lines in the plane

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2003年第6期13卷 463-485页

作者： Linhart, C Halperin, D Hanniel, I Har-Peled, S Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

Given a finite set L of lines in the plane we wish to compute the zone of an additional curve gamma in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that are crossed by gamma, where gamma is not given in advance but rather provided on-line portion by portion. This problem is motivated by the computation of the area bisectors of a polygonal set in the plane. We present four algorithms which solve this problem efficiently and exactly (giving precise results even on degenerate input). Our main algorithm is a novel approach based on the binary space partition technique. We implemented all four algorithms. We present implementation details, comparison of performance, and a discussion of the advantages and shortcomings of each of the proposed algorithms.

关键词： arrangements of lines zone on-line algorithms binary space partition half-plane intersection convex hulls

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling with tight deadlines

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期295卷 251-261页

作者： Koo, CY Lamb, TW Ngan, TW Sadakane, K To, KK Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Univ Maryland Dept Comp Sci College Pk MD 20742 USA Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

This paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a uni-processor system. It has been known for long that in such a setting, no on-line algorithm is 1-competitive (i.e., optimal) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines;indeed, no algorithm can be better than k-competitive, where k is the importance ratio of the jobs. Recent work, however, reveals that the competitive ratio can be improved to a constant if the on-line scheduler is equipped with a processor 0(l) times faster (J. ACM 47(4) (2000) 617), and further to one when using a processor O(log k) times faster (Proc. 12th Ann. ACM-SIAM Symp. on Discrete algorithms, 2001, p. 755). This paper presents a new on-line algorithm for scheduling jobs with tight deadlines and shows that it is 1-competitive when using a processor that is only 0(l) times faster. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms competitive analysis deadline scheduling

来源：评论

学校读者我要写书评

暂无评论

Sharing video on demand

引用

DISCRETE APPLIED MATHEMATICS 2003年第1期129卷 3-30页

作者： Bar-Noy, A Garay, JA Herzberg, A IBM Corp TJ Watson Res Ctr Yorktown Hts NY USA Brooklyn Coll Dept Comp & Informat Sci Brooklyn NY 11210 USA Bell Labs Lucent Technol Murray Hill NJ 07974 USA IBM Corp Haifa Res Ctr IL-61336 Tel Aviv Israel

We formulate the problem of video on demand (VOD) from a resource allocation perspective. We introduce the decision element into a movie vending environment, which complements the current approaches. In contrast with the traditional resource allocation problems (e.g., machine scheduling), the problem possesses the distinctive batching property, which stands for the feasibility of several requests being served by one resource. First, we investigate the problem in an on-line fashion, namely, having to accept or reject a request for a movie without any knowledge about future requests. We show upper and lower bounds on the competitive ratio of on-line movie scheduling algorithms for a variety of scenarios depending on the notification time. In particular, when the length of the movie and the notification time on requests are linearly related, we present a simple competitive algorithm. Second, we propose a new approach-Shared VOD-which gives a more balanced functionality/price tradeoff than the two popular approaches full VOD and near VOD. In this approach, several users may share the same channels, but the movies are selected by the users themselves. In this framework, we evaluate a variety of on-line channel allocation algorithms under "typical" conditions. We compare these strategies to the off-line strategy, and show that the algorithm we introduce substantially outperforms the rest. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： video on demand resource allocation on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling with tight deadlines

On-line scheduling with tight deadlines

引用

26th International Symposium on Mathematical Foundations of Computer Science

关键词： on-line algorithms competitive analysis deadline scheduling

来源：评论

学校读者我要写书评

暂无评论

Sharing video on demand

Sharing video on demand

引用

作者： Bar-Noy, Amotz Garay, Juan A. Herzberg, Amir Computer and Information Science Department Brooklyn College 2900 Bedford Avenue Brooklyn NY 11210 United States Bell Labs - Lucent Technologies 600 Mountain Avenue Murray Hill NJ 07974 United States IBM Haifa Research Center 2 Weizmann Street Tel-Aviv 61336 Israel

We formulate the problem of video on demand (VOD) from a resource allocation perspective. We introduce the decision element into a movie vending environment, which complements the current approaches. In contrast with the traditional resource allocation problems (e.g., machine scheduling), the problem possesses the distinctive batching property, which stands for the feasibility of several requests being served by one resource. First, we investigate the problem in an on-line fashion, namely, having to accept or reject a request for a movie without any knowledge about future requests. We show upper and lower bounds on the competitive ratio of on-line movie scheduling algorithms for a variety of scenarios depending on the notification time. In particular, when the length of the movie and the notification time on requests are linearly related, we present a simple competitive algorithm. Second, we propose a new approach - Shared VOD - which gives a more balanced functionality/price tradeoff than the two popular approaches full VOD and near VOD. In this approach, several users may share the same channels, but the movies are selected by the users themselves. In this framework, we evaluate a variety of on-line channel allocation algorithms under "typical" conditions. We compare these strategies to the off-line strategy, and show that the algorithm we introduce substantially outperforms the rest. © 2002 Elsevier Science B.V. All rights reserved.

关键词： Competitive analysis on-line algorithms Resource allocation Video on demand

来源：评论

学校读者我要写书评

暂无评论

The online set cover problem 03

The online set cover problem

引用

Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

作者： Noga Alon Baruch Awerbuch Yossi Azar Tel Aviv University Tel Aviv Israel Johns Hopkins University Baltimore MD

ISBN: (纸本)9781581136746

Let X=[1,2,•••,n] be a ground set of n elements, and let S be a family of subsets of X, |S|=m, with a positive cost cS associated with each S ∈ *** the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one-by-one. Once a new element is given, the algorithm has to cover it by some set of S containing it. We assume that the elements of X and the members of S are known in advance to the algorithm, however, the set X' ⊆ X of elements given by the adversary is not known in advance to the algorithm. (In general, X' may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let C denote the family of sets in S that the algorithm chooses. At the end of the game the adversary also produces (off-line) a family of sets COPT that covers X'. The performance of the algorithm is the ratio between the cost of C and the cost of COPT. The maximum ratio, taken over all input sequences, is the competitive ratio of the *** present an O(log m log n) competitive deterministic algorithm for the problem, and establish a nearly matching Ω(log n log m/log log m + log log n) lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting the fractional solution they supply into a deterministic online algorithm.

关键词： competitive analysis randomized rounding set-cover on-line algorithms derandomization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：