WEKO3
アイテム
{"_buckets": {"deposit": "5a49d4ea-9645-4d4d-8c6e-6ebf8a12b5ed"}, "_deposit": {"id": "19567", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "19567"}, "status": "published"}, "_oai": {"id": "oai:soar-ir.repo.nii.ac.jp:00019567", "sets": ["1222"]}, "author_link": ["105070", "105071"], "item_1628147817048": {"attribute_name": "出版タイプ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_ab4af688f83e57aa", "subitem_version_type": "AM"}]}, "item_6_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2015", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "1", "bibliographicPageEnd": "87", "bibliographicPageStart": "67", "bibliographicVolumeNumber": "29", "bibliographic_titles": [{"bibliographic_title": "JOURNAL OF COMBINATORIAL OPTIMIZATION"}]}]}, "item_6_description_20": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "The bin packing problem has been extensively studied and numerous variants have been considered. The k-item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522-550, 1975). In addition to the formulation of the classical bin packing problem, this problem imposes a cardinality constraint that the number of items packed into each bin must be at most k. For the online setting of this problem, in which the items are given one by one, Babel et al. (Discret Appl Math 143: 238-251, 2004) provided lower boundsv root 2 approximate to 1.41421 and 1.5 on the asymptotic competitive ratio for k = 2 and 3, respectively. For k \u003e= 4, some lower bounds (e.g., by van Vliet (Inf Process Lett 43:277-284, 1992) for the online bin packing problem, i.e., a problem without cardinality constraints, can be applied to this problem. In this paper we consider the online k-item bin packing problem. First, we improve the previous lower bound 1.41421 to 1.42764 for k = 2. Moreover, we propose a new method to derive lower bounds for general k and present improved bounds for various cases of k \u003e= 4. For example, we improve 1.33333 to 1.5 for k = 4, and 1.33333 to 1.47058 for k = 5.", "subitem_description_type": "Abstract"}]}, "item_6_description_30": {"attribute_name": "資源タイプ(コンテンツの種類)", "attribute_value_mlt": [{"subitem_description": "Article", "subitem_description_type": "Other"}]}, "item_6_description_5": {"attribute_name": "引用", "attribute_value_mlt": [{"subitem_description": "JOURNAL OF COMBINATORIAL OPTIMIZATION. 29(1): 67-87 (2015)", "subitem_description_type": "Other"}]}, "item_6_link_3": {"attribute_name": "信州大学研究者総覧へのリンク", "attribute_value_mlt": [{"subitem_link_text": "Fujiwara, Hiroshi", "subitem_link_url": "http://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html"}]}, "item_6_link_67": {"attribute_name": "WoS", "attribute_value_mlt": [{"subitem_link_text": "Web of Science", "subitem_link_url": "http://gateway.isiknowledge.com/gateway/Gateway.cgi?\u0026GWVersion=2\u0026SrcAuth=ShinshuUniv\u0026SrcApp=ShinshuUniv\u0026DestLinkType=FullRecord\u0026DestApp=WOS\u0026KeyUT=000350684400005"}]}, "item_6_publisher_4": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "SPRINGER"}]}, "item_6_relation_48": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_name": [{"subitem_relation_name_text": "10.1007/s10878-013-9679-8"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.1007/s10878-013-9679-8", "subitem_relation_type_select": "DOI"}}]}, "item_6_rights_62": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "The original publication is available at www.springerlink.com"}]}, "item_6_select_64": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_select_item": "author"}]}, "item_6_source_id_35": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "1382-6905", "subitem_source_identifier_type": "ISSN"}]}, "item_6_source_id_39": {"attribute_name": "NII ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "1382-6905", "subitem_source_identifier_type": "ISSN"}]}, "item_6_text_69": {"attribute_name": "wosonly authkey", "attribute_value_mlt": [{"subitem_text_value": "Bin packing problem@@@Online algorithm@@@Competitive analysis@@@Cardinality constraint"}]}, "item_6_text_70": {"attribute_name": "wosonly keywords", "attribute_value_mlt": [{"subitem_text_value": "ALGORITHMS"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Fujiwara, Hiroshi"}], "nameIdentifiers": [{"nameIdentifier": "105070", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Kobayashi, Koji"}], "nameIdentifiers": [{"nameIdentifier": "105071", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2018-03-09"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "Improved_Lower_Bounds_for_the_Online_Bin_Packing_Problem_with_Cardinality_Constraints.pdf", "filesize": [{"value": "176.1 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_note", "mimetype": "application/pdf", "size": 176100.0, "url": {"label": "Improved_Lower_Bounds_for_the_Online_Bin_Packing_Problem_with_Cardinality_Constraints.pdf", "url": "https://soar-ir.repo.nii.ac.jp/record/19567/files/Improved_Lower_Bounds_for_the_Online_Bin_Packing_Problem_with_Cardinality_Constraints.pdf"}, "version_id": "6fccf47c-3381-4cde-979f-75f5c4461f09"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Bin packing problem", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Online algorithm", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Competitive analysis", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Cardinality constraint", "subitem_subject_scheme": "Other"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "journal article", "resourceuri": "http://purl.org/coar/resource_type/c_6501"}]}, "item_title": "Improved lower bounds for the online bin packing problem with cardinality constraints", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Improved lower bounds for the online bin packing problem with cardinality constraints", "subitem_title_language": "en"}]}, "item_type_id": "6", "owner": "1", "path": ["1222"], "permalink_uri": "http://hdl.handle.net/10091/00020328", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2018-03-09"}, "publish_date": "2018-03-09", "publish_status": "0", "recid": "19567", "relation": {}, "relation_version_is_last": true, "title": ["Improved lower bounds for the online bin packing problem with cardinality constraints"], "weko_shared_id": -1}
Improved lower bounds for the online bin packing problem with cardinality constraints
http://hdl.handle.net/10091/00020328
http://hdl.handle.net/10091/0002032869840a07-33c6-472a-a7c5-7f715e2f28b2
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2018-03-09 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | Improved lower bounds for the online bin packing problem with cardinality constraints | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Bin packing problem | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Online algorithm | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Competitive analysis | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Cardinality constraint | |||||
資源タイプ | ||||||
資源 | http://purl.org/coar/resource_type/c_6501 | |||||
タイプ | journal article | |||||
著者 |
Fujiwara, Hiroshi
× Fujiwara, Hiroshi× Kobayashi, Koji |
|||||
信州大学研究者総覧へのリンク | ||||||
氏名 | Fujiwara, Hiroshi | |||||
URL | http://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html | |||||
出版者 | ||||||
出版者 | SPRINGER | |||||
引用 | ||||||
内容記述タイプ | Other | |||||
内容記述 | JOURNAL OF COMBINATORIAL OPTIMIZATION. 29(1): 67-87 (2015) | |||||
書誌情報 |
JOURNAL OF COMBINATORIAL OPTIMIZATION 巻 29, 号 1, p. 67-87, 発行日 2015 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | The bin packing problem has been extensively studied and numerous variants have been considered. The k-item bin packing problem is one of the variants introduced by Krause et al. (J ACM 22:522-550, 1975). In addition to the formulation of the classical bin packing problem, this problem imposes a cardinality constraint that the number of items packed into each bin must be at most k. For the online setting of this problem, in which the items are given one by one, Babel et al. (Discret Appl Math 143: 238-251, 2004) provided lower boundsv root 2 approximate to 1.41421 and 1.5 on the asymptotic competitive ratio for k = 2 and 3, respectively. For k >= 4, some lower bounds (e.g., by van Vliet (Inf Process Lett 43:277-284, 1992) for the online bin packing problem, i.e., a problem without cardinality constraints, can be applied to this problem. In this paper we consider the online k-item bin packing problem. First, we improve the previous lower bound 1.41421 to 1.42764 for k = 2. Moreover, we propose a new method to derive lower bounds for general k and present improved bounds for various cases of k >= 4. For example, we improve 1.33333 to 1.5 for k = 4, and 1.33333 to 1.47058 for k = 5. | |||||
資源タイプ(コンテンツの種類) | ||||||
内容記述タイプ | Other | |||||
内容記述 | Article | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 1382-6905 | |||||
DOI | ||||||
識別子タイプ | DOI | |||||
関連識別子 | https://doi.org/10.1007/s10878-013-9679-8 | |||||
関連名称 | 10.1007/s10878-013-9679-8 | |||||
権利 | ||||||
権利情報 | The original publication is available at www.springerlink.com | |||||
出版タイプ | ||||||
出版タイプ | AM | |||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
WoS | ||||||
表示名 | Web of Science | |||||
URL | http://gateway.isiknowledge.com/gateway/Gateway.cgi?&GWVersion=2&SrcAuth=ShinshuUniv&SrcApp=ShinshuUniv&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000350684400005 |