ログイン
言語:

WEKO3

  • トップ
  • コミュニティ
  • ランキング
AND
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

{"_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": ["1221:1222"]}, "author_link": ["105070", "105071"], "item_1628147817048": {"attribute_name": "\u51fa\u7248\u30bf\u30a4\u30d7", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_ab4af688f83e57aa", "subitem_version_type": "AM"}]}, "item_6_biblio_info_6": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "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": "\u6284\u9332", "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": "\u8cc7\u6e90\u30bf\u30a4\u30d7\uff08\u30b3\u30f3\u30c6\u30f3\u30c4\u306e\u7a2e\u985e\uff09", "attribute_value_mlt": [{"subitem_description": "Article", "subitem_description_type": "Other"}]}, "item_6_description_5": {"attribute_name": "\u5f15\u7528", "attribute_value_mlt": [{"subitem_description": "JOURNAL OF COMBINATORIAL OPTIMIZATION. 29(1): 67-87 (2015)", "subitem_description_type": "Other"}]}, "item_6_link_3": {"attribute_name": "\u4fe1\u5dde\u5927\u5b66\u7814\u7a76\u8005\u7dcf\u89a7\u3078\u306e\u30ea\u30f3\u30af", "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": "\u51fa\u7248\u8005", "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": "\u6a29\u5229", "attribute_value_mlt": [{"subitem_rights": "The original publication is available at www.springerlink.com"}]}, "item_6_select_64": {"attribute_name": "\u8457\u8005\u7248\u30d5\u30e9\u30b0", "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": "\u8457\u8005", "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": "\u30d5\u30a1\u30a4\u30eb\u60c5\u5831", "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": "\u30ad\u30fc\u30ef\u30fc\u30c9", "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": "\u8a00\u8a9e", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "\u8cc7\u6e90\u30bf\u30a4\u30d7", "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": "\u30bf\u30a4\u30c8\u30eb", "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": ["1221/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}
  1. 060 工学部
  2. 0601 学術論文

Improved lower bounds for the online bin packing problem with cardinality constraints

http://hdl.handle.net/10091/00020328
69840a07-33c6-472a-a7c5-7f715e2f28b2
名前 / ファイル ライセンス アクション
Improved_Lower_Bounds_for_the_Online_Bin_Packing_Problem_with_Cardinality_Constraints.pdf Improved_Lower_Bounds_for_the_Online_Bin_Packing_Problem_with_Cardinality_Constraints.pdf (176.1 kB)
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

WEKO 105070

Fujiwara, Hiroshi

Search repository
Kobayashi, Koji

× Kobayashi, Koji

WEKO 105071

Kobayashi, Koji

Search repository
信州大学研究者総覧へのリンク
氏名 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
戻る
0
views
See details
Views

Versions

Ver.1 2021-03-01 07:30:00.618255
Show All versions

Share

Mendeley CiteULike Twitter Facebook Print Addthis

Cite as

Export

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by CERN Data Centre & Invenio


Powered by CERN Data Centre & Invenio