Search this article in Google Scholar


分類 国際会議
著者名 (author) Satoshi Fujita
英文著者名 (author)
編者名 (editor)
編者名 (英文)
キー (key)
表題 (title) On-Line Grid-Packing with a Single Active Grid
表題 (英文)
書籍・会議録表題 (booktitle) Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, LNCS
書籍・会議録表題(英文)
巻数 (volume) 2387
号数 (number)
ページ範囲 (pages) 476-483
組織名 (organization)
出版元 (publisher)
出版元 (英文)
出版社住所 (address)
刊行月 (month) August
出版年 (year) 2002
付加情報 (note) Singapore
注釈 (annote) Acceptance rate: 62/106 = 58%, http://www.springerlink.com/content/bxcbhl8ut7mkyqc1/
内容梗概 (abstract) In this paper, we study the problem of packing rectangular items into a minimum number of square grids in an on-line manner with a single active grid, where the size of each grid is m x m for some positive integer m, and the height and the width of each item are positive integers smaller than or equal to m, respectively. We first prove that the asymptotic competitive ratio of an optimal on-line algorithm is at least 23/11. We then propose an on-line algorithm that achieves a competitive ratio O((loglogm)2).
論文電子ファイル Not available.


[1-32]  Satoshi Fujita, ``On-Line Grid-Packing with a Single Active Grid,'' In Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, LNCS, vol. 2387, pp. 476-483, August 2002. (Singapore)

@inproceedings{1_32,
    author = {Satoshi Fujita},
    author_e = {},
    editor = {},
    editor_e = {},
    title = {On-Line Grid-Packing with a Single Active Grid},
    title_e = {},
    booktitle = {Computing and Combinatorics, 8th Annual International
    Conference, COCOON 2002, LNCS},
    booktitle_e = {},
    volume = {2387},
    number = {},
    pages = {476-483},
    organization = {},
    publisher = {},
    publisher_e = {},
    address = {},
    month = {August},
    year = {2002},
    note = {Singapore},
    annote = {Acceptance rate: 62/106 = 58%, http://www.springerlink.com/content
    /bxcbhl8ut7mkyqc1/}
}

This site is maintained by Distributed System Laboratory.

PMAN 2.5.5 - Paper MANagement system / (C) 2002-2008, Osamu Mizuno / All rights reserved.