{"_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"]}, "item_6_biblio_info_6": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "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": "\u6284\u9332", "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": "\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. 31(2): 463-490 (2016)", "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=000368686900002"}]}, "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-014-9762-9"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "http://doi.org/10.1007/s10878-014-9762-9", "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": "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": "\u8457\u8005", "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": "\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": "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_free", "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": "\u30ad\u30fc\u30ef\u30fc\u30c9", "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": "\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": "On the best possible competitive ratio for the multislope ski-rental problem", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "On the best possible competitive ratio for the multislope ski-rental problem"}]}, "item_type_id": "6", "owner": "1", "path": ["1221/1222"], "permalink_uri": "http://hdl.handle.net/10091/00020327", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "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": 3}