{"created":"2021-03-01T06:22:39.462855+00:00","id":19566,"links":{},"metadata":{"_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":["1221: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'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.","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_url":"http://gateway.isiknowledge.com/gateway/Gateway.cgi?&GWVersion=2&SrcAuth=ShinshuUniv&SrcApp=ShinshuUniv&DestLinkType=FullRecord&DestApp=WOS&KeyUT=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_source_id_35":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1382-6905","subitem_source_identifier_type":"ISSN"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Fujiwara, Hiroshi"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kitano, Takuma"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Fujito, Toshihiro"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-03-09"}],"displaytype":"detail","filename":"On_the_Best_Possible_Competitive_Ratio_for_the_Multislope_Ski-Rental_Problem.pdf","filesize":[{"value":"313.4 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","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"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2018-03-09"},"publish_date":"2018-03-09","publish_status":"0","recid":"19566","relation_version_is_last":true,"title":["On the best possible competitive ratio for the multislope ski-rental problem"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2022-12-14T04:30:55.748671+00:00"}