{"created":"2023-05-15T14:21:42.372902+00:00","id":3457,"links":{},"metadata":{"_buckets":{"deposit":"648a987f-bda2-4a2a-8e92-15d004d57cb8"},"_deposit":{"created_by":3,"id":"3457","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"3457"},"status":"published"},"_oai":{"id":"oai:bunkyo.repo.nii.ac.jp:00003457","sets":["1:26:202"]},"author_link":["4442"],"item_5_biblio_info_13":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"1997-01-01","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"147","bibliographicPageStart":"135","bibliographicVolumeNumber":"18","bibliographic_titles":[{"bibliographic_title":"情報研究"},{"bibliographic_title":"Information and Communication Studies","bibliographic_titleLang":"en"}]}]},"item_5_date_43":{"attribute_name":"作成日","attribute_value_mlt":[{"subitem_date_issued_datetime":"2012-01-17","subitem_date_issued_type":"Created"}]},"item_5_description_12":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"　Suppose we are given a poset(partially ordered set) P = (V,?), a real-valued weight w(e) associated with each element e ∈ V and a positive integer k. We consider the problem which asks to find an ideal of size k of P such that the maximum element weight in the ideal is the minimum for all ideals that can be constructed from P. We call this problem the minimax k-ideal problem. In this paper we propose two fast algorithms: a greedy algorithm and a threshold algorithm. Combining these algorithms, we accomplish the best available bound O(min{n log n +m, (m + n)log n}) for this problem; the two bounds in this expression are, respectively, due to the greedy algorithm and the threshold algorithm, where |V|=n and m is the number of arcs of the Hasse diagram representing the given poset. This ruesult shows that this problem does not have an Ω(n log n + m) lower bound in spite of the fact that the minimum-range k-ideal problem, which is a general problem of the minimax k-ideal problem, has an Ω( n log n + m) lower bound.","subitem_description_type":"Abstract"}]},"item_5_publisher_16":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"文教大学"}]},"item_5_source_id_19":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"03893367","subitem_source_identifier_type":"ISSN"}]},"item_5_text_39":{"attribute_name":"本文言語","attribute_value_mlt":[{"subitem_text_value":"英語"}]},"item_5_text_42":{"attribute_name":"ID","attribute_value_mlt":[{"subitem_text_value":"BKSJ180007"}]},"item_5_text_8":{"attribute_name":"所属機関","attribute_value_mlt":[{"subitem_text_value":"文教大学情報学部"}]},"item_5_version_type_35":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Nemoto,Toshio"}],"nameIdentifiers":[{"nameIdentifier":"4442","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-03-24"}],"displaytype":"detail","filename":"BKSJ180007.pdf","filesize":[{"value":"641.0 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"BKSJ180007.pdf","url":"https://bunkyo.repo.nii.ac.jp/record/3457/files/BKSJ180007.pdf"},"version_id":"ff6ef076-b4e7-49fb-9787-fadf370e7d88"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"departmental bulletin paper","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Algorithms for the Minimax k-Ideal Problem","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Algorithms for the Minimax k-Ideal Problem"}]},"item_type_id":"5","owner":"3","path":["202"],"pubdate":{"attribute_name":"公開日","attribute_value":"2012-01-17"},"publish_date":"2012-01-17","publish_status":"0","recid":"3457","relation_version_is_last":true,"title":["Algorithms for the Minimax k-Ideal Problem"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2024-08-08T01:09:08.207986+00:00"}