WEKO3
アイテム
{"_buckets": {"deposit": "671f345c-70cd-47f6-83ff-9f3340fbb3ad"}, "_deposit": {"id": "19566", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "19566"}, "status": "published"}, "_oai": {"id": "oai:soar-ir.repo.nii.ac.jp:00019566", "sets": ["1222"]}, "author_link": ["105067", "105068", "105069"], "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": "2016", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "2", "bibliographicPageEnd": "490", "bibliographicPageStart": "463", "bibliographicVolumeNumber": "31", "bibliographic_titles": [{"bibliographic_title": "JOURNAL OF COMBINATORIAL OPTIMIZATION"}]}]}, "item_6_description_20": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options besides the pure rent and buy options. In this problem the hardness of an instance, which is the setting of options, significantly affects the player\u0027s performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than cannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems.", "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. 31(2): 463-490 (2016)", "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=000368686900002"}]}, "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-014-9762-9"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://doi.org/10.1007/s10878-014-9762-9", "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": "Online algorithm@@@Competitive analysis@@@Online optimization@@@Ski-rental problem@@@Mathematical programming"}]}, "item_6_text_70": {"attribute_name": "wosonly keywords", "attribute_value_mlt": [{"subitem_text_value": "STRATEGIES"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Fujiwara, Hiroshi"}], "nameIdentifiers": [{"nameIdentifier": "105067", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Kitano, Takuma"}], "nameIdentifiers": [{"nameIdentifier": "105068", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Fujito, Toshihiro"}], "nameIdentifiers": [{"nameIdentifier": "105069", "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": "On_the_Best_Possible_Competitive_Ratio_for_the_Multislope_Ski-Rental_Problem.pdf", "filesize": [{"value": "313.4 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_note", "mimetype": "application/pdf", "size": 313400.0, "url": {"label": "On_the_Best_Possible_Competitive_Ratio_for_the_Multislope_Ski-Rental_Problem.pdf", "url": "https://soar-ir.repo.nii.ac.jp/record/19566/files/On_the_Best_Possible_Competitive_Ratio_for_the_Multislope_Ski-Rental_Problem.pdf"}, "version_id": "7d9e7a39-873b-4c45-975e-8b0afca95801"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "Online algorithm", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Competitive analysis", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Online optimization", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Ski-rental problem", "subitem_subject_scheme": "Other"}, {"subitem_subject": "Mathematical programming", "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": "On the best possible competitive ratio for the multislope ski-rental problem", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "On the best possible competitive ratio for the multislope ski-rental problem", "subitem_title_language": "en"}]}, "item_type_id": "6", "owner": "1", "path": ["1222"], "permalink_uri": "http://hdl.handle.net/10091/00020327", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2018-03-09"}, "publish_date": "2018-03-09", "publish_status": "0", "recid": "19566", "relation": {}, "relation_version_is_last": true, "title": ["On the best possible competitive ratio for the multislope ski-rental problem"], "weko_shared_id": -1}
On the best possible competitive ratio for the multislope ski-rental problem
http://hdl.handle.net/10091/00020327
http://hdl.handle.net/10091/000203271af99f81-bfb2-42e1-a150-b0e9c58225f1
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2018-03-09 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | On the best possible competitive ratio for the multislope ski-rental problem | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Online algorithm | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Competitive analysis | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Online optimization | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Ski-rental problem | |||||
キーワード | ||||||
主題Scheme | Other | |||||
主題 | Mathematical programming | |||||
資源タイプ | ||||||
資源 | http://purl.org/coar/resource_type/c_6501 | |||||
タイプ | journal article | |||||
著者 |
Fujiwara, Hiroshi
× Fujiwara, Hiroshi× Kitano, Takuma× Fujito, Toshihiro |
|||||
信州大学研究者総覧へのリンク | ||||||
氏名 | Fujiwara, Hiroshi | |||||
URL | http://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html | |||||
出版者 | ||||||
出版者 | SPRINGER | |||||
引用 | ||||||
内容記述タイプ | Other | |||||
内容記述 | JOURNAL OF COMBINATORIAL OPTIMIZATION. 31(2): 463-490 (2016) | |||||
書誌情報 |
JOURNAL OF COMBINATORIAL OPTIMIZATION 巻 31, 号 2, p. 463-490, 発行日 2016 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options besides the pure rent and buy options. In this problem the hardness of an instance, which is the setting of options, significantly affects the player's performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than cannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems. | |||||
資源タイプ(コンテンツの種類) | ||||||
内容記述タイプ | Other | |||||
内容記述 | Article | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 1382-6905 | |||||
DOI | ||||||
識別子タイプ | DOI | |||||
関連識別子 | https://doi.org/10.1007/s10878-014-9762-9 | |||||
関連名称 | 10.1007/s10878-014-9762-9 | |||||
権利 | ||||||
権利情報 | 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=000368686900002 |