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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Relative loss bounds for on-line density estimation with the exponential family of distributions

引用

MACHINE LEARNING 2001年第3期43卷 211-246页

作者： Azoury, KS Warmuth, MK San Francisco State Univ Coll Business San Francisco CA 94132 USA Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA

We consider on-line density estimation with a parameterized density from the exponential family. The on-line algorithm receives one example at a time and maintains a parameter that is essentially an average of the past examples. After receiving an example the algorithm incurs a loss, which is the negative log-likelihood of the example with respect to the current parameter of the algorithm. An off-line algorithm can choose the best parameter based on all the examples. We prove bounds on the additional total loss of the on-line algorithm over the total loss of the best off-line parameter. These relative loss bounds hold for an arbitrary sequence of examples. The goal is to design algorithms with the best possible relative loss bounds. We use a Bregman divergence to derive and analyze each algorithm. These divergences are relative entropies between two exponential distributions. We also use our methods to prove relative loss bounds for linear regression.

关键词： relative loss bounds worst-case loss bounds on-line algorithms exponential family of distributions linear regression Bregman divergences

来源：评论

学校读者我要写书评

暂无评论

The shuffling buffer

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2001年第5期11卷 555-572页

作者： Devillers, O Guigue, P INRIA Sophia Antipolis F-06902 Sophia Antipolis France

The complexity of randomized incremental algorithms is analyzed with the assumption of a random order of the input. To guarantee this hypothesis, the n data have to be known in advance in order to be mixed what contradicts with the on-line nature of the algorithm. We present the shuffling buffer technique to introduce sufficient randomness to guarantee an improvement on the worst case complexity by knowing only k data in advance. Typically, an algorithm with O(n(2)) worst-case complexity and O(n) or O(n log n) randomized complexity has an O(n(2)logk/k) complexity for the shuffling buffer. We illustrate this with binary search trees, the number of Delaunay triangles or the number of trapezoids in a trapezoidal map created during an incremental construction.

关键词： computational and structural complexity randomized algorithms on-line algorithms computational geometry

来源：评论

学校读者我要写书评

暂无评论

Vector balancing games with aging

引用

JOURNAL OF COMBINATORIAL THEORY SERIES A 2001年第2期95卷 219-233页

作者： Doerr, B Univ Kiel Math Seminar 2 D-24098 Kiel Germany

In this article we study an extension of the vector balancing game investigated by Spencer and Olson (which corresponds to the on-line version of the discrepancy problem for matrices). We assume that decisions in earlier rounds become less and less important as the game continues. For an aging parameter q greater than or equal to 1 we define the current move to be q times more important than the previous one. We consider two variants of this problem: First, the objective is a balanced partition at the end of the game, and second, it is to ensure a balanced partition throughout the game. We concentrate on the case q greater than or equal to 2. We give an optimal solution for the first problem and a nearly optimal one for the second. (C) 2001 Academic Press.

关键词： vector balancing games on-line algorithms discrepancy

来源：评论

学校读者我要写书评

暂无评论

On-line randomized call control revisited

引用

SIAM JOURNAL ON COMPUTING 2001年第1期31卷 86-112页

作者： Leonardi, S Marchetti-Spaccamela, A Presciutti, A Rosén, A Univ Roma La Sapienza Dipartimento Informat Sistemist I-00198 Rome Italy Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

We consider the problem of on-line call admission and routing on trees and meshes. Previous work gave randomized on-line algorithms for these problems and proved that they have optimal ( up to constant factors) competitive ratios. However, these algorithms can obtain very low profit with high probability. We investigate the question of devising for these problems on-line competitive algorithms that also guarantee a good solution with good probability. We give a new family of randomized algorithms with asymptotically optimal competitive ratios and good probability to get a profit close to the expectation. We complement these results by providing bounds on the probability of any optimally competitive randomized on-line algorithm for the problems we consider to get a profit close to the expectation. To the best of our knowledge, this is the rst study of the relationship between the tail distribution and the competitive ratio of randomized on-line benefit algorithms.

关键词： on-line algorithms competitive analysis randomized algorithms call admission control

来源：评论

学校读者我要写书评

暂无评论

Dynamic traitor tracing

引用

JOURNAL OF CRYPTOLOGY 2001年第3期14卷 211-223页

作者： Fiat, A Tassa, T Tel Aviv Univ Sch Math Sci Dept Comp Sci IL-69978 Tel Aviv Israel Algorithm Res Ltd Petah Tiqwa Israel

Traitor tracing schemes were introduced to combat the typical piracy scenario whereby pirate decoders (or access control smartcards) are manufactured and sold by pirates to illegal subscribers. Those traitor tracing schemes, however, are ineffective for the currently less common scenario where a pirate publishes the periodical access control keys on the Internet or, alternatively, simply rebroadcasts the content via an independent pirate network. This new piracy scenario may become especially attractive (to pirates) in the context of broadband multicast over the Internet. In this paper we consider the consequences of this type of piracy and offer countermeasures. We introduce the concept of dynamic traitor tracing which is a practical and efficient tool to combat this type of piracy.

关键词： broadcast encryption traitor tracing watermarking imprinting pay TV on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

A new lower bound for the list update problem in the partial cost model

引用

THEORETICAL COMPUTER SCIENCE 2001年第1期268卷 3-16页

作者： Ambühl, C Gärtner, B von Stengel, B Univ London London Sch Econ & Polit Sci Dept Math London WC2A 2AE England Swiss Fed Inst Technol Inst Theoret Comp Sci CH-8092 Zurich Switzerland

The optimal competitive ratio for a randomized online list update algorithm is known to be at least 1.5 and at most 1.6, but the remaining gap is not yet closed. We present a new lower bound of 1.50084 for the partial cost model. The construction is based on game trees with incomplete information, which seem to be generally useful for the competitive analysis of online algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms analysis of algorithms competitive analysis list-update

来源：评论

学校读者我要写书评

暂无评论

On-line bin-stretching

引用

THEORETICAL COMPUTER SCIENCE 2001年第1期268卷 17-41页

作者： Azar, Y Regev, O Tel Aviv Univ Dept Comp Sci Sch Math IL-69978 Tel Aviv Israel

We are given a sequence of items that can be packed into m unit size bins. In the classical bin packing problem we fix the size of the bins and try to pack the items in the minimum number of such bins. In contrast, in the bin-stretching problem we fix the number of bins and try to pack the items while stretching the size of the bins as least as possible. We present two on-line algorithms for the bin-stretching problem that guarantee a stretching factor of 5/3 for any number ni of bins. We then combine the two algorithms and design an algorithm whose stretching factor is 1.625 for any m. The analysis for the performance of this algorithm is tight. The best lower bound for any algorithm is 4/3 for any m greater than or equal to2. We note that the bin-stretching problem is also equivalent to the classical scheduling (load balancing) problem in which the value of the makespan (maximum load) is known in advance. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms approximation algorithms bin stretching load balancing scheduling bin-packing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：