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

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

来源：评论

学校读者我要写书评

暂无评论

Tight bounds for dynamic storage allocation

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1996年第1期9卷 155-166页

作者： Luby, MG Naor, JS Orda, A TECHNION ISRAEL INST TECHNOL DEPT COMP SCIIL-32000 HAIFAISRAEL TECHNION ISRAEL INST TECHNOL DEPT ELECT ENGNIL-32000 HAIFAISRAEL

This paper is concerned with on-line storage allocation to processes in a dynamic environment. This problem has been extensively studied in the past. We provide a new, tighter bound for the competitive ratio of the well-known First Fit algorithm. This bound is obtained by considering a new parameter, namely the maximum number of concurrent active processes. We observe that this bound is also a lower bound on the competitive ratio of any deterministic on-line algorithm. Our second contribution is an on-line allocation algorithm that uses coloring techniques. We show that the competitive ratio of this algorithm is the same as that of First Fit. Furthermore, we indicate that this algorithm may be advantageous in certain applications. Our third contribution is to analyze the performance of randomized algorithms for this problem. We obtain lower bounds on the competitive ratio that are close to the best deterministic upper bounds.

关键词： on-line algorithms memory management dynamic storage allocation bandwidth allocation First Fit interval graph

来源：评论

学校读者我要写书评

暂无评论

Competitive distributed decision-making

引用

ALGORITHMICA 1996年第2期16卷 133-150页

作者： Deng, XT Papadimitriou, CH UNIV CALIF SAN DIEGO DEPT COMP SCI LA JOLLA CA 92093 USA

We study several natural problems in distributed decision-making from the standpoint of competitive analysis;in these problems incomplete information is a result of the distributed nature of the problem, as opposed to the on-line mode of decision making that was heretofore prevalent in this area In several simple situations of distributed scheduling, the competitive ratio can be computed exactly, and the different ratios can be used as a measure of the value of information and communication between decision-makers. In a more general distributed scheduling situation, we give tight upper and lower bounds on the competitive ratio achievable in the deterministic case, and give an optimal randomized algorithm with a much better competitive ratio.

关键词： on-line algorithms distributed computing load balancing distributed scheduling

来源：评论

学校读者我要写书评

暂无评论

Randomized algorithms for the on-line minimum matching problem on Euclidean space

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1995年第1-2期58卷 19-32页

作者： Tsai, YT Tang, CY Chen, YY NATL TSING HUA UNIV DEPT COMP SCIHSINCHU 300TAIWAN

Suppose we are given two sets R and B, each of n points in the plane. Define the cost of a matching to be the teal distance of the edges in the, matching. The minimum matching problem on Euclidean space is to find a complete bipartite matching which has the minimum cost on Euclidean space. In this paper, we are interested in the on-line minimum matching problem on Euclidean space. We assume the set R is known, but the points of set B are revealed one by one. When a point of set B arrives, we must decide what match to make involving the point. None of the matches can be changed after they are made. The on-line minimum matching problem on Euclidean space tries to minimize the cost of the complete bipartite matching that we find. This paper proposes a family of randomized algorithms, Algorithm RM(m) (1 less than or equal to m less than or equal to n), for solving this problem. When a point in the set B arrived, Algorithm RM(m) randomly chooses at most m unmatched points in the set R, and adds the minimum edge between the arriving point and the chosen points to the matching. In each decision step, the algorithm only runs in O(m) time, which is superior to the known non-randomized algorithms for this problem. In this paper, we show that Algorithm RM(m) is not a competitive on-line algorithm for 1 less than or equal to m less than or equal to n-1. However, we further show that if 2n is large, the average cost incurred by Algorithm RM(m) (1 less than or equal to m less than or equal to n) is bounded by O(root n) times the average cost of the optimal Euclidean minimum matching.

关键词： analysis of algorithms on-line algorithms randomized algorithms the on-line minimum matching problem competitive analysis average case analysis

来源：评论

学校读者我要写书评

暂无评论

Optimal parameters for on-line arithmetic

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1995年第1-2期56卷 11-18页

作者： Walter, CD Computation Department U.M.I.S.T. Manchester M60 1QD PO Box 88 Sackville Street United Kingdom

Some general techniques are given for constructing divergent examples for on-line arithmetic operations whose parameters are chosen beyond the optimal ones which converge. They are applied in particular to the cases o... 详细信息

关键词： computer arithmetic multiplication division square root on-line algorithms redundant number systems recurrence relations

来源：评论

学校读者我要写书评

暂无评论

Geometric two-server algorithms

引用

Information Processing Letters 1995年第6期53卷 355-355页

作者： El-Yaniv, R. Kleinberg, J. Department of Computer Science University of Toronto Canada Laboratory for Computer Science N43-334 MIT 545 Technology Square Cambridge MA 02139 USA

For two servers in d -dimensional space under the L 1 metric, we give an optimal 2-competitive algorithm which uses constant time and space per request. This considerably extends the class of metric spaces for which an optimal, fast two-server algorithm is known; previously, the only such spaces were those that could be embedded in a tree. The algorithm itself can be seen as a higher-dimensional generalization of the “double-coverage” strategy of Chrobak et al.

关键词： Analysis of algorithms on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for preemptive on-line scheduling

引用

OPERATIONS RESEARCH LETTERS 1995年第3期18卷 127-131页

作者： Chen, B vanVliet, A Woeginger, GJ ERASMUS UNIV ROTTERDAM INST ECONOMETR3000 DR ROTTERDAMNETHERLANDS GRAZ TECH UNIV INST MATHA-8010 GRAZAUSTRIA

We investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. We derive an approximation algorithm with worst-case guarantee m(m)/(m(m) - (m - 1)(m)) for every m greater than or equal to 2, which increasingly tends to e/(e - 1) approximate to 1.58 as m --> infinity. Moreover, we prove that for no m greater than or equal to 2 there does exist any approximation algorithm with a better worst-case guarantee.

关键词： scheduling preemption on-line algorithms worst-case bounds

来源：评论

学校读者我要写书评

暂无评论

AN ON-line ALGORITHM FOR NAVIGATING IN AN UNKNOWN ENVIRONMENT

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1993年第3期3卷 227-244页

作者： Chan, Kwong-Fai Lam, Tak Wah Mass Transit Railway Corp Commercial Syst Dev Hong Kong Hong Kong Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

Suppose that a robot is required to traverse a two-dimensional scene with impenetrable rectangular obstacles. The robot has no information about the obstacles in advance and the size, location, and orientation of each obstacle in the scene are arbitrary, yet the robot can see and move in any direction. In this paper we construct an on-line algorithm for the robot to determine an obstacle-free path to its destination dynamically. The primary concern for such on-line algorithm is the competitiveness coefficient which essentially compares the actual distance traversed to the length of the shortest path. We show that if the aspect ratio of every rectangular obstacle in the scene is bounded by a constant r, then our algorithm achieves the optimal competitiveness coefficient which is r/2 + 1.

关键词： on-line algorithms motion-planning competitiveness shortest paths computational geometry

来源：评论

学校读者我要写书评

暂无评论

Limitations Concerning On-line Scheduling algorithms for Overloaded Real-Time Systems

引用

IFAC Proceedings Volumes 1991年第2期24卷 123-125页

作者： S.K. Baruah L.E. Rosier Department of Computer Sciences The University of Texas at Austin Austin TX 78712-1188 USA

With respect to on-line scheduling algorithms that must direct the service of sporadic task requests we quantify the benefit of possessing knowledge concerning the timing of future events. Consider the problem of preemptively scheduling sporadic task requests in a uniprocessor environment. If a task request is successfully scheduled to completion, a value equal to the request’s execution time is obtained; otherwise a value of zero is obtained. We prove that no on-line scheduling algorithm can guarantee a cumulative value greater than (√2—1) times the value obtainable by a clairvoyant scheduler, i.e., we prove a performance guarantee limitation of 41.4%. Over intervals where the loading factor does not exceed one the performance guarantee limitation is 100%. As the loading factor exceeds one we show that the performance guarantee limitation immediately drops to 61.8%. and as the loading factor increases from one to two, we show that the performance guarantee limitation falls from 61.8%; to 41.4%. Beyond two the performance guarantee limitation remains at 41.4%.

关键词： Real time computer systems scheduling theory on-line algorithms performance bounds optimal performance

来源：评论

学校读者我要写书评

暂无评论

AN OPTIMAL ONline ALGORITHM FOR METRICAL TASK SYSTEM

引用

JOURNAL OF THE ACM 1992年第4期39卷 745-763页

作者： BORODIN, A LINIAL, N SAKS, ME HEBREW UNIV JERUSALEM INST COMP SCI & MATHJERUSALEMISRAEL IBM CORP ALMADEN RES CTRSAN JOSECA 95114 UNIV CALIF SAN DIEGO DEPT COMP SCISAN DIEGOCA 92103

In practice, almost all dynamic systems require decisions to be made on-line, without full knowledge of their future impact on the system. A general model for the processing of sequences of tasks is introduced, and a general on-line decision algorithm is developed. It is shown that, for an important class of special cases, this algorithm is optimal among all on-line algorithms. Specifically, a task system (S, d) for processing sequences of tasks consists of a set S of states and a cost matrix d where d(i, j) is the cost of changing from state i to state j (we assume that d satisfies the triangle inequality and all diagonal entries are 0). The cost of processing a given task depends on the state of the system. A schedule for a sequence T1, T2, ..., T(k) of tasks is a sequence s1, s2, ..., s(k) of states where si is the state in which T1 is processed;the cost of a schedule is the sum of all task processing costs and state transition costs incurred. An on-line scheduling algorithm is one that chooses s(i) only knowing T1T2 ... T(i). Such an algorithm is w-competitive if, on any input task sequence, its cost is within an additive constant of w times the optimal offline schedule cost. The competitive ratio w(S,d) is the infimum w for which there is a w-competitive on-line scheduling algorithm for (S, d). It is shown that w(S, d) = 2 Absolute value of S - 1 for every task system in which d is symmetric, and w(S, d) = O(Absolute value of S2) for every task system. Finally, randomized on-line scheduling algorithms are introduced. It is shown that for the uniform task system (in which d(i, j) = 1 for all i, j), the expected competitive ratio wBAR(S, d) O(log Absolute value of S).

关键词： competitive analysis on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：