A PROOF OF THE OPTIMALITY OF THE MIN PAGING ALGORITHM USING LINEAR-PROGRAMMING DUALITY

被引：3

作者：

COHEN, A

BURKHARD, WA

机构：

[1] Gemini Storage Systems Laboratory, Department of Computer Science and Engineering, University of California, San Diego, La Jolla

来源：

OPERATIONS RESEARCH LETTERS | 1995年 / 18卷 / 01期

关键词：

ANALYSIS OF ALGORITHMS; PAGING; LINEAR PROGRAMMING; DUALITY; ASSIGNMENT PROBLEM;

D O I：

10.1016/0167-6377(95)00021-B

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

A linear programming formulation of the page replacement problem is used for proving the optimality of the MIN algorithm in a novel way. We describe an algorithm for constructing a solution for the dual problem such that the cost of this solution equals the cost of the MIN solution for the primal problem, thus proving the optimality of the MIN solution for paging, and the optimality of our algorithm for the paging dual (which is a special case of the assignment dual).

引用

页码：7 / 13

页数：7

共 8 条

[1] A STUDY OF REPLACEMENT ALGORITHMS FOR A VIRTUAL-STORAGE COMPUTER [J].

BELADY, LA .

IBM SYSTEMS JOURNAL, 1966, 5 (02) :78-&

[2]

Coffman Jr E. G., 1973, OPERATING SYSTEMS TH

[3]

CRAMA Y, 1994, INT J FLEXIBLE MANUF, V6, P35

[4] COMPETITIVE PAGING-ALGORITHMS [J].

FIAT, A ;

KARP, RM ;

LUBY, M ;

MCGEOCH, LA ;

SLEATOR, DD ;

YOUNG, NE .

JOURNAL OF ALGORITHMS, 1991, 12 (04) :685-699

[5] EVALUATION TECHNIQUES FOR STORAGE HIERARCHIES [J].

MATTSON, RL ;

GECSEI, J ;

SLUTZ, DR ;

TRAIGER, IL .

IBM SYSTEMS JOURNAL, 1970, 9 (02) :78-&

[6]

MCGEOCH LA, 1989, CMUCS89122 CARN MEL

[7]

Schrijver A., 1986, THEORY LINEAR INTEGE

[8]

YOUNG N, 1991, THESIS PRINCETON U P

← 1 →