DocumentCode
2178725
Title
Combinatorial analysis of an efficient algorithm for processor and storage allocation
Author
Coffman, E.G., Jr. ; Leung, Joseph Y T
fYear
1977
fDate
Oct. 31 1977-Nov. 2 1977
Firstpage
214
Lastpage
221
Abstract
A combinatorial problem related to storage allocation is analyzed. The problem falls into a class of NP-complete, one-dimensional bin-packing problems. We propose an iterative approximation algorithm and show that it is superior to an earlier heuristic presented for this problem. The bulk of the paper is devoted to the proof of a worst-case performance bound.
Keywords
Algorithm design and analysis; Approximation algorithms; Bismuth; Computer science; Iterative algorithms; Performance analysis; Polynomials; Processor scheduling; Scheduling algorithm; Terminology;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1977., 18th Annual Symposium on
Conference_Location
Providence, RI, USA
ISSN
0272-5428
Type
conf
DOI
10.1109/SFCS.1977.8
Filename
4567945
Link To Document