{"_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}