WEKO3
アイテム
{"_buckets": {"deposit": "f0a7f32b-c88b-4642-8eff-d860b691f8bf"}, "_deposit": {"id": "44551", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "44551"}, "status": "published"}, "_oai": {"id": "oai:tsukuba.repo.nii.ac.jp:00044551", "sets": ["5509", "6269"]}, "item_5_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2017-11", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "62", "bibliographicPageStart": "53", "bibliographicVolumeNumber": "699", "bibliographic_titles": [{"bibliographic_title": "Theoretical computer science"}]}]}, "item_5_creator_3": {"attribute_name": "著者別名", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "小林, 佑輔"}], "nameIdentifiers": [{"nameIdentifier": "178202", "nameIdentifierScheme": "WEKO"}]}]}, "item_5_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "We consider the following zero-sum game related to the knapsack problem. Given an instance of the knapsack problem, Alice chooses a knapsack solution and Bob, knowing Alice’s solution, chooses a cardinalityk. Then, Alice obtains a payoff equal to the ratio of the profit of the best kitems in her solution to that of the best solution of size at most k. For α\u003e0, a knapsack solution is called α-robustif it guarantees payoffα. If Alice adopts a deterministic strategy, the objective of Alice is to find a max-robust knapsack solution. By applying the argument in Kakimura and Makino[6]for robustness in general independence systems, a (1/√μ)-robust solution exists and is found in polynomial time, where μis the exchangeability of the independence system.\nIn the present paper, we address randomized strategies for this zero-sum game. Random-ized strategies in robust independence systems are introduced by Matuschke, Skutella, and Soto[11]and they presented a randomized strategy with (1/ ln4)-robustness for a certain class of independence systems. The knapsack problem, however, does not belong to this class. We first establish the intractability of the knapsack problem by showing an instance such that the robustness of an arbitrary randomized strategy is both O((loglogμ)/ logμ)and O((loglogρ)/ logρ), where ρ:=(thesizeofamaximumfeasibleset)(thesizeofaminimuminfeasibleset)−1. We then exhibit the power of randomness by designing two randomized strategies with robustness Ω (1/ logμ) and Ω (1/ logρ), respectively, which substantially improve upon that of known deterministic strategies and almost attain the above upper bounds. It is also noteworthy that our strategy applies to not only the knapsack problem but also independence systems for which an (approximately) optimal solution under a cardinality constraint is computable.", "subitem_description_type": "Abstract"}]}, "item_5_publisher_27": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "Elsevier"}]}, "item_5_relation_11": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type_id": {"subitem_relation_type_id_text": "10.1016/j.tcs.2016.12.019", "subitem_relation_type_select": "DOI"}}]}, "item_5_rights_12": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "© 2016. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/"}]}, "item_5_select_15": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_select_item": "author"}]}, "item_5_source_id_7": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0304-3975", "subitem_source_identifier_type": "ISSN"}]}, "item_5_source_id_9": {"attribute_name": "書誌レコードID", "attribute_value_mlt": [{"subitem_source_identifier": "AA00862688", "subitem_source_identifier_type": "NCID"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Kobayashi, Yusuke"}], "nameIdentifiers": [{"nameIdentifier": "178200", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Takazawa, Kenjiro"}], "nameIdentifiers": [{"nameIdentifier": "178201", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2019-12-01"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "TCS_699-53.pdf", "filesize": [{"value": "127.9 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_11", "mimetype": "application/pdf", "size": 127900.0, "url": {"label": "TCS_699-53", "url": "https://tsukuba.repo.nii.ac.jp/record/44551/files/TCS_699-53.pdf"}, "version_id": "e270e1ba-eef1-4d8d-954d-d9e8d7126f7f"}]}, "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": "Randomized strategies for cardinality robustness in the knapsack problem", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Randomized strategies for cardinality robustness in the knapsack problem"}]}, "item_type_id": "5", "owner": "1", "path": ["5509", "6269"], "permalink_uri": "http://hdl.handle.net/2241/00149426", "pubdate": {"attribute_name": "公開日", "attribute_value": "2017-12-25"}, "publish_date": "2017-12-25", "publish_status": "0", "recid": "44551", "relation": {}, "relation_version_is_last": true, "title": ["Randomized strategies for cardinality robustness in the knapsack problem"], "weko_shared_id": 5}
Randomized strategies for cardinality robustness in the knapsack problem
http://hdl.handle.net/2241/00149426
http://hdl.handle.net/2241/0014942699f5bfda-9ac5-4a3f-aed5-cdfc1a96f1ed
名前 / ファイル | ライセンス | アクション |
---|---|---|
TCS_699-53 (127.9 kB)
|
Item type | Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2017-12-25 | |||||
タイトル | ||||||
タイトル | Randomized strategies for cardinality robustness in the knapsack problem | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源 | http://purl.org/coar/resource_type/c_6501 | |||||
タイプ | journal article | |||||
著者 |
Kobayashi, Yusuke
× Kobayashi, Yusuke× Takazawa, Kenjiro |
|||||
著者別名 |
小林, 佑輔
× 小林, 佑輔 |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | We consider the following zero-sum game related to the knapsack problem. Given an instance of the knapsack problem, Alice chooses a knapsack solution and Bob, knowing Alice’s solution, chooses a cardinalityk. Then, Alice obtains a payoff equal to the ratio of the profit of the best kitems in her solution to that of the best solution of size at most k. For α>0, a knapsack solution is called α-robustif it guarantees payoffα. If Alice adopts a deterministic strategy, the objective of Alice is to find a max-robust knapsack solution. By applying the argument in Kakimura and Makino[6]for robustness in general independence systems, a (1/√μ)-robust solution exists and is found in polynomial time, where μis the exchangeability of the independence system. In the present paper, we address randomized strategies for this zero-sum game. Random-ized strategies in robust independence systems are introduced by Matuschke, Skutella, and Soto[11]and they presented a randomized strategy with (1/ ln4)-robustness for a certain class of independence systems. The knapsack problem, however, does not belong to this class. We first establish the intractability of the knapsack problem by showing an instance such that the robustness of an arbitrary randomized strategy is both O((loglogμ)/ logμ)and O((loglogρ)/ logρ), where ρ:=(thesizeofamaximumfeasibleset)(thesizeofaminimuminfeasibleset)−1. We then exhibit the power of randomness by designing two randomized strategies with robustness Ω (1/ logμ) and Ω (1/ logρ), respectively, which substantially improve upon that of known deterministic strategies and almost attain the above upper bounds. It is also noteworthy that our strategy applies to not only the knapsack problem but also independence systems for which an (approximately) optimal solution under a cardinality constraint is computable. |
|||||
書誌情報 |
Theoretical computer science 巻 699, p. 53-62, 発行日 2017-11 |
|||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 0304-3975 | |||||
書誌レコードID | ||||||
収録物識別子タイプ | NCID | |||||
収録物識別子 | AA00862688 | |||||
DOI | ||||||
識別子タイプ | DOI | |||||
関連識別子 | 10.1016/j.tcs.2016.12.019 | |||||
権利 | ||||||
権利情報 | © 2016. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ | |||||
著者版フラグ | ||||||
値 | author | |||||
出版者 | ||||||
出版者 | Elsevier |