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

On page migration and other relaxed task systems

THEORETICAL COMPUTER SCIENCE 2001年第1期268卷 43-66页

作者： Bartal, Y Charikar, M Indyk, P Stanford Univ Dept Comp Sci Stanford CA 94305 USA Int Comp Sci Inst Berkeley CA 94704 USA

This paper is concerned with the page migration (or file migration) problem (Black and Sleator, Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989) as part of a large class of on-line problems. The page migration problem deals with the management of pages residing in a network of processors. In the classical problem there is only one copy of each page which is accessed by different processors over time. The page is allowed to be migrated between processors. However a migration incurs higher communication cost than an access (proportionally to the page size). The problem is that of deciding when and where to migrate the page in order to lower access costs. A more general setting is the k-page migration problem where we wish to maintain k copies of the page. The page migration problems are concerned with a dilemma common to many on-line problems: determining when it is beneficial to make configuration changes. We deal with the relaxed task systems model which captures a large class of problems of this type, that can be described as the generalization of some original task system problem (Borodin et al., J. ACM 39(4) (1992) 745-763). Given a c-competitive algorithm for a task system we show how to obtain a deterministic O(c(2)) and randomized O(c) competitive algorithms for the corresponding relaxed task system. The result implies deterministic algorithms for k-page migration by using k-server (Manasse et al., J. algorithms 11(2) (1990) 208-230) algorithms, and for network leasing by using generalized Steiner tree algorithms (Awerbuch et al., Proc 7th Ann. ACM-SIAM Symp. on Discrete algorithms, January 1996, pp. 68-74), as well as providing solutions for natural generalizations of other problems (e.g. storage rearrangement (Fiat et al., Proc. 36th Ann. IEEE Symp. on Foundations of Computer Science, October 1995, pp. 392-403). We further study some special cases of the k-page migration problem and get optimal deterministic a

关键词： on-line algorithms page migration relaxed task systems

来源：评论

学校读者我要写书评

暂无评论

Vector balancing games with aging

引用

Electronic Notes in Discrete Mathematics 2001年 10卷 90-92页

作者： Doerr, Benjamin Mathematisches Seminar Christian-Albrechts-Universität zu Kiel D-24098 Kiel Ludewig-Meyn-Str. 4 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 earl... 详细信息

关键词： Discrepancy on-line algorithms Vector balancing games

来源：评论

学校读者我要写书评

暂无评论

Simple algorithms for the on-line multidimensional dictionary and related problems

引用

ALGORITHMICA 2000年第2期28卷 255-267页

作者： Gonzalez, TF Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

The on-line multidimensional dictionary problem consists of executing on-line any sequence of the following operations: INSERT(p), DELETE(p), and MEMBERSHIP(p), where p is any (ordered) d-tuple (Or String with d elements, or points in d-space where the dimensions have been ordered). We introduce a clean structure based on balanced binary search trees, which we call multidimensional balanced binary search trees, to represent the set of d-tuples. We present algorithms for each of the above operations that take O(d + log n) time, where n is the current number of d-tuples in the set, and each INSERT and DELETE operation requires no more than a constant number of rotations. Our structure requires dn words to represent the input, plus O(n) pointers and data indicating the first component where pairs of d-tuples differ. This information, which can be easily updated, enables us to test for MEMBERSHIP efficiently. Other operations that can be performed efficiently in our multidimensional balanced binary search trees are: print in lexicographic order(O (dn) time), find the (lexicographically) smallest or largest d-tuple (O(log n) time), and concatenation (O (d + log n) time). Finding the (lexicographically) kth smallest or largest d-tuple can also be implemented efficiently (O(log n) time), at the expense of adding an integer value at each node.

关键词： multidimensional dictionary on-line algorithms data structures

来源：评论

学校读者我要写书评

暂无评论

Improved randomized on-line algorithms for the list update problem

引用

SIAM JOURNAL ON COMPUTING 1998年第3期27卷 682-693页

作者： Albers, S Max Planck Inst Informat D-66123 Saarbrucken Germany

The best randomized on-line algorithms known so far for the list update problem achieve a competitiveness of root 3 approximate to 1.73. In this paper we present a new family of randomized online algorithms that beat this competitive ratio. Our improved algorithms are called TIMESTAMP algorithms and achieve a competitiveness of max {2 - p,1 + p(2 - p)}, for any real number p epsilon [0,1]. Setting p = (3 - root 5)/2, we obtain a phi-competitive algorithm, where phi = (1 + root 5)/2 approximate to 1.62 is the golden ratio. TIMESTAMP algorithms coordinate the movements of items using some information on past requests. We can reduce the required information at the expense of increasing the competitive ratio. We present a very simple version of the TIMESTAMP algorithms that is 1.68-competitive. The family of TIMESTAMP algorithms also includes a new deterministic 2-competitive on-line algorithm that is different from the MOVE-TO-FRONT RULE.

关键词： linear lists on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Competitive analysis of randomized paging algorithms

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期234卷 203-218页

作者： Achlioptas, D Chrobak, M Noga, J Univ Calif Riverside Dept Math Riverside CA 92521 USA Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA

The paging problem is defined as follows: we are given a two-level memory system, in which one level is a fast memory, called cache, capable of holding k items, and the second level is an unbounded but slow memory. At each given time step, a request to an item is issued. Given a request to an item p, a miss occurs if p is not present in the fast memory. In response to a miss, we need to choose an item q in the cache and replace it by p. The choice of q needs to be made on-line, without the knowledge of future requests. The objective is to design a replacement strategy with a small number of misses. In this paper we use competitive analysis to study the performance of randomized on-line paging algorithms. Our goal is to show how the concept of work functions, used previously mostly for the analysis of deterministic algorithms, can also be applied, in a systematic fashion, to the randomized case. We present two results: we first show that the: competitive ratio of the marking algorithm is exactly 2H(k) - 1. Previously, it was known to be between H-k and 2(Hk). Then we provide a new, H-k-competitive algorithm for paging. Our algorithm, as well as its analysis, is simpler than the known algorithm by McGeoch and Sleator. Another advantage of our algorithm is that it can be implemented with complexity bounds independent of the number of past requests: O(k(2) log k) memory and O(k(2)) time per request. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms analysis of algorithms competitive analysis paging randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A decomposition theorem for task systems and bounds for randomized server problems

引用

SIAM JOURNAL ON COMPUTING 2000年第5期30卷 1624-1661页

作者： Blum, A Karloff, H Rabani, Y Saks, M Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel DIMACS Piscataway NJ USA Rutgers State Univ Dept Math Piscataway NJ 08854 USA Univ Calif San Diego Dept Comp Sci & Engn La Jolla CA 92093 USA

A lower bound of Omega(root log k/log log k) is proved for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (having at least k + 1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of (log log k) for arbitrary metric spaces [H. J. Karlo, Y. Rabani, and Y. Ravid, SIAM J. Comput., 23 (1994), pp. 293-312] and more closely approaches the conjectured lower bound of ( log k). For the server problem on k + 1 equally spaced points on a line, which corresponds to a natural motion-planning problem, a lower bound of (log k/log log k) is obtained. The results are deduced from a general decomposition theorem for a simpler version of both the k-server and the metrical task system problems, called the pursuit-evasion game. It is shown that if a metric space M can be decomposed into two spaces M-L and M-R such that the distance between them is sufficiently large compared to their diameter, then the competitive ratio for this game on M can be expressed nearly exactly in terms of the ratios on each of the two subspaces. This yields a divide-and-conquer approach to bounding the competitive ratio of a space.

关键词： lower bounds randomized algorithms k-server task systems on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling with setup costs

引用

INFORMATION PROCESSING LETTERS 2000年第1-2期73卷 61-68页

作者： Gambosi, G Nicosia, G Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Univ Roma Tre Dipartimento Automat & Informat I-00146 Rome Italy

This paper deals with an on-line scheduling problem where tasks belong to a given set of c task types and are to be assigned to one of the m machines in order to minimize the maximum completion time. If a task of a certain type is assigned to a machine that has just completed the execution of a task of the same type, then it can be processed immediately. Otherwise, there is a setup time associated with switching the machine to a different task type. A suitable version of the classical List Scheduling algorithm is analyzed. A new algorithm is also proposed and an upper bound on its competitive ratio is introduced. Finally, lower bound on the competitive ratio for any on-line algorithm is derived. (C) 2000 Published by Elsevier Science B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

On the competitiveness of the move-to-front rule

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期242卷 313-325页

作者： Martínez, C Roura, S Univ Politecn Cataluna Dept Llenguages & Sistemes Informat E-08034 Barcelona Spain

We consider the list access problem and show that one questionable assumption in the original cost model presented by Sleator and Tarjan (1985) and subsequent literature allowed for several competitiveness;results of the move-to-front rule (MTF). We present an off-line algorithm for the list access problem and prove that, under a. more realistic cost model, no on-line algorithm can be c-competitive for any constant c, MTT: included. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： competitive analysis on-line algorithms list update problem move-to-front rule

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling on a single machine: maximizing the number of early jobs

引用

OPERATIONS RESEARCH LETTERS 2000年第5期27卷 193-197页

作者： Hoogeveen, H Potts, CN Woeginger, GJ Univ Utrecht Inst Informat & Comp Sci NL-3584 CH Utrecht Netherlands Univ Southampton Fac Math Studies Southampton SO17 1BJ Hants England Graz Univ Technol Inst Math B A-8010 Graz Austria

This note deals with the scheduling problem of maximizing the number of early jobs on a single machine. We investigate the on-line version of this problem in the Preemption-Restart model. This means that jobs may be preempted, but preempting results in all the work done on this job so far being lost. Thus, if the job is restarted, then it has to be done from scratch. We prove that the shortest remaining processing time (SRPT) rule yields an on-line algorithm with competitive ratio 1/2. Moreover, we show that there does not exist an on-line algorithm with a better performance guarantee. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： combinatorial problems on-line algorithms competitive analysis worst-case bounds single-machine scheduling

来源：评论

学校读者我要写书评

暂无评论

Multiprocessor scheduling with rejection

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2000年第1期13卷 64-78页

作者： Bartal, Y Leonardi, S Marchetti-Spaccamela, A Sgall, J Stougie, L Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Univ Rome La Sapienza Dipartimento Informat Sistemist I-00198 Rome Italy AS CR Math Inst Prague 11567 1 Czech Republic Charles Univ Fac Math & Phys Dept Appl Math Prague Czech Republic Hebrew Univ Jerusalem Inst Comp Sci Jerusalem Israel Eindhoven Univ Technol Dept Math NL-5600 MB Eindhoven Netherlands

We consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by m identical parallel machines and a set of n jobs, with each job characterized by a processing time and a penalty. In the on-line version the jobs become available one by one and we have to schedule or reject a job before we have any information about future jobs. The objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of rejected jobs. The main result is a 1 + phi approximate to 2.618 competitive algorithm for the on-line version of the problem, where phi is the golden ratio. A matching lower bound shows that this is the best possible algorithm working for all m. For fixed m we give improved bounds;in particular, for m = 2 we give a phi approximate to 1.618 competitive algorithm, which is best possible. For the off-line problem we present a fully polynomial approximation scheme for fixed m and a polynomial approximation scheme for arbitrary m. Moreover, we present an approximation algorithm which runs in time O(n log n) for arbitrary m and guarantees a 2 - 1/m approximation ratio.

关键词： multiprocessor scheduling on-line algorithms competitive analysis approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：