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

Competitive on-line scheduling of continuous-media streams

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2002年第2期64卷 219-248页

作者： Garofalakis, M Ioannidis, Y Özden, B Silberschatz, A Bell Labs Murray Hill NJ 07974 USA Univ Athens Dept Informat & Telecommun GR-15784 Athens Greece

Multimedia applications require a guaranteed level of service for accessing continuous-media data. To obtain such guarantees, the database server where the data are residing must employ an admission control scheme to limit the number of clients that can be served concurrently. We investigate the problem of on-line admission control, where the decision of whether to accept or reject a request must be made without any knowledge about future requests. Employing competitive analysis techniques, we address the problem in its most general form with the following key contributions: (1) We prove a tight upper bound on the competitive ratio of the conventional Work-Conserving (WC) policy, showing that it is within a factor 1+Delta/1-p of the optimal clairvoyant strategy, where Delta is the ratio of the maximum to minimum request length (i.e., time duration), and p is the maximum fraction of the server's bandwidth that a request can demand;(2) we prove a lower bound of Omega(log Delta/1-p) on the competitive ratio of any deterministic or randomized admission control scheme, demonstrating an exponential gap between greedy and optimal on-line solutions;(3) we propose simple deterministic schemes based on the idea of bandwidth prepartitioning that guarantee competitive ratios within a small constant factor of log Delta (i.e., they are provably near-optimal) if p < 1 /[log Delta];and (4) we introduce a novel admission control policy that partitions the server bandwidth based on the expected popularities of different request lengths and experimentally demonstrate its benefits compared to WC. (C) 2002 Elsevier Science (USA).

关键词： multimedia databases resource scheduling admission control on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Lower bounds in on-line geometric searching

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2001年第1期18卷 37-53页

作者： Schuierer, S Univ Freiburg Inst Informat D-79110 Freiburg Germany

We present a new technique to prove lower bounds for geometric on-line searching problems. We assume that a target of unknown location is hidden somewhere in a known environment and a searcher is trying to find it. We are interested in lower bounds on the competitive ratio of the search strategy, that is, the ratio of the distance traveled by the searcher to the distance of the target. The technique we present is applicable to a number of problems, such as biased searching on m rays and on-line construction of on-line algorithms. For each problem we prove tight lower bounds. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms lower bounds competitive analysis navigation autonomous mobile robots computational geometry

来源：评论

学校读者我要写书评

暂无评论

A new upper bound on the work function algorithm for the k-server problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第2期39卷 509-518页

作者： Zhang, Wenming Cheng, Yongxi Northwest Univ Sch Econ & Management Xian 710127 Peoples R China Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China

The k-server problem was introduced by Manasse et al. (in: Proceedings of the 20th annual ACM symposium on theory of computing, Chicago, Illinois, USA, pp 322-333, 1988), and is one of the most famous and well-studied online problems. Koutsoupias and Papadimitriou (J ACM42(5):971-983, 1995) showed that the work function algorithm (WFA) has a competitive ratio of at most 2k - 1 for the k-server problem. In this paper, by proposing a potential function that is different from the one in Koutsoupias and Papadimitriou (1995), we show that the WFA has a competitive ratio of at most n - 1, where n is the number of points in the metric space. When n < 2k, this ratio is less than 2k - 1.

关键词： Competitive analysis k-server problem on-line algorithms Work function

来源：评论

学校读者我要写书评

暂无评论

On-line construction of the upper envelope of triangles and surface patches in three dimensions

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 1996年第6期5卷 303-320页

作者： Boissonnat, JD Dobrindt, KTG INST NATL RECH INFORMAT & AUTOMAT F-06902 SOPHIA ANTIPOLISFRANCE UNIV UTRECHT VAKGRP INFORMAT3508 TB UTRECHTNETHERLANDS

In this paper, we describe a randomized incremental algorithm for computing the upper envelope (i.e., the pointwise maximum) of a set of n triangles in three dimensions, This algorithm is an on-line algorithm. It is structure-sensitive: the expected cost of inserting the n-th triangle is O(log n Sigma(r=1)(n) tau(r)/r(2)) and depends on the expected size tau(r) of an intermediate result for r triangles, Since tau(r) can be Theta(r(2) alpha(r)) in the worst case, this cost is bounded in the worst case by O(n alpha(n) log n), (The expected behaviour is analyzed by averaging over all possible orderings of the input.) The main new characteristics is the use of a two-level history graph. (The history graph is an auxiliary data structure maintained by randomized incremental algorithms.) Our algorithm is fairly simple and appears to be efficient in practice, It extends to surfaces and surface patches of fixed maximum algebraic degree.

关键词： computational geometry on-line algorithms randomized incremental algorithms upper envelope hidden surface removal

来源：评论

学校读者我要写书评

暂无评论

On the influence of lookahead in competitive paging algorithms

引用

ALGORITHMICA 1997年第3期18卷 283-305页

作者： Albers, S UNIV SAARLAND D-6600 SAARBRUCKENGERMANY

We introduce a new model of lookahead for on-line paging algorithms and study several algorithms using this model. A paging algorithm is on-line with strong lookahead l if it sees the present request and a sequence of future requests that contains l pairwise distinct pages. We show that strong lookahead has practical as well as theoretical importance and improves the competitive factors of on-line paging algorithms. This is the first model of lookahead having such properties. In addition to lower bounds we present a number of deterministic and randomized on-line paging algorithms with strong lookahead which are optimal or nearly optimal.

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

来源：评论

学校读者我要写书评

暂无评论

Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates

引用

OPERATIONS RESEARCH LETTERS 2001年第3期29卷 141-148页

作者： Kaminsky, P Simchi-Levi, D Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA MIT Engn Syst Div Cambridge MA USA MIT Dept Civil & Environm Engn Cambridge MA USA

In the single machine mean completion time problem with release dates, a set of jobs has to be processed non-preemptively on a single machine. No job can be processed before its release date, and the objective is to determine a sequence of the jobs on the machine which minimizes the sum of the completion times of all jobs. In this paper, we prove the asymptotic optimality of the shortest processing time among available jobs algorithm, in which at the completion time of any job, the next job to be scheduled is the shortest job among all those released but not yet processed. This algorithm is particularly attractive because it falls in the class of easy to implement and computationally inexpensive on-line algorithms. (C) 2001 Elsevier Science BY. All rights reserved.

关键词： scheduling asymptotic analysis on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight bounds for bandwidth allocation on two links

引用

DISCRETE APPLIED MATHEMATICS 2005年第2期148卷 181-188页

作者： Epstein, L Univ Haifa Dept Math IL-31905 Haifa Israel

We study on-line bandwidth allocation on two parallel links. Motivated by issues of quality of service and fair resource allocation, the goal is to maximize the load of the least loaded link. We analyze several models... 详细信息

关键词： on-line algorithms scheduling related machines bandwidth allocation

来源：评论

学校读者我要写书评

暂无评论

Scheduling Jobs on Grid Processors

引用

ALGORITHMICA 2010年第4期57卷 819-847页

作者： Boyar, Joan Favrholdt, Lene M. Univ So Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark

We study a new kind of on-line bin packing, motivated by a problem arising when scheduling jobs on the Grid. In this bin packing problem, the set of items is given at the beginning, and variable-sized bins arrive one by one. We analyze the problem using both the competitive ratio and the relative worst order ratio, observing that the two measures often lead to different conclusions. A closely related problem was introduced by Zhang (Discrete Appl. Math. 72:193-197, 1997). Our main result answers a question posed in that paper in the affirmative: we give an algorithm with a competitive ratio strictly better than 2, for our problem as well as Zhang's problem. For identical bins, the new algorithm has essentially the same performance as FFD (First-Fit-Decreasing).

关键词： Grid scheduling problem Zhang's bin packing problem on-line algorithms First-Fit-Decreasing

来源：评论

学校读者我要写书评

暂无评论

On-line maximum matching in complete multi-partite graphs with an application to optical networks

引用

DISCRETE APPLIED MATHEMATICS 2016年 199卷 123-136页

作者： Shalom, Mordechai Wong, Prudence W. H. Zaks, Shmuel TelHai Acad Coll IL-12210 Upper Galilee Israel Univ Liverpool Dept Comp Sci Liverpool Merseyside England Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

Finding a maximum matching in a graph is a classical problem. The on-line versions of the problem in which the vertices and/or edges of the graph are given one at a time and an algorithm has to calculate a matching incrementally have been studied for more than two decades. Many variants of the problem are considered in the literature. The pioneering work (Karp, 1990) considers a bipartite graph where the vertices of one part are revealed one at a time together with their incident edges. In this work we consider maximal d-colorable graphs which are exactly the complete d-partite graphs. The vertices arrive one at a time together with their incident edges, or equivalently with their corresponding colors in some given d-coloring of the graph. We present an optimal 2/3-competitive deterministic algorithm for this on-line problem. This problem is closely related to that of minimizing the cost of line terminals in star topology optical network. We consider lightpaths arriving in an on-line fashion on a given star network. Our result implies a tight 10/9-competitive algorithm for finding a wavelength assignment minimizing the cost of line terminals in such a network. (C) 2014 Published by Elsevier B.V.

关键词： on-line algorithms Maximum matching Multi-partite graphs Optical networks Switching cost

来源：评论

学校读者我要写书评

暂无评论

The accommodating function: A generalization of the competitive ratio

引用

SIAM JOURNAL ON COMPUTING 2001年第1期31卷 233-258页

作者： Boyar, J Larsen, KS Nielsen, MN Odense Univ Univ So Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark

A new measure, the accommodating function, for the quality of on-line algorithms is presented. The accommodating function, which is a generalization of both the competitive ratio and the competitive ratio on accommodating sequences, measures the quality of an on-line algorithm as a function of the resources that would be sufficient for an optimal off-line algorithm to fully grant all requests. More precisely, if we have some amount of resources n, the function value at alpha is the usual ratio ( still on some fixed amount of resources n), except that input sequences are restricted to those where the optimal off-line algorithm will not obtain a better result by having more than the amount alphan of resources. The accommodating functions for three specific on-line problems are investigated: a variant of bin packing in which the goal is to maximize the number of items put in n bins, the seat reservation problem, and the problem of optimizing total ow time when preemption is allowed. We also show that when trying to distinguish between two algorithms, the decision as to which one performs better cannot necessarily be made from the competitive ratio or the competitive ratio on accommodating sequences alone. For the variant of bin-packing considered, we show that Worst-Fit has a strictly better competitive ratio than First-Fit, while First-Fit has a strictly better competitive ratio on accommodating sequences than Worst-Fit.

关键词： on-line algorithms performance measures competitive analysis restricted adversaries bin packing seat reservations flow time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：