{"created":"2023-05-15T14:21:42.064925+00:00","id":3450,"links":{},"metadata":{"_buckets":{"deposit":"d32c358c-6a05-4ab1-96e3-df15524cd7d8"},"_deposit":{"created_by":3,"id":"3450","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"3450"},"status":"published"},"_oai":{"id":"oai:bunkyo.repo.nii.ac.jp:00003450","sets":["1:26:201"]},"author_link":["4431"],"item_5_biblio_info_13":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"1996-01-01"},"bibliographicPageEnd":"274","bibliographicPageStart":"265","bibliographicVolumeNumber":"17","bibliographic_titles":[{"bibliographic_title":"情報研究"},{"bibliographic_title":"Information and Communication Studies"}]}]},"item_5_date_43":{"attribute_name":"作成日","attribute_value_mlt":[{"subitem_date_issued_datetime":"2012-01-17"}]},"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(v) associated with each element v ∈ V and a positive integer K. We consider the problem which asks to find an ideal of size K of P such that the sum of the weights of the elements of this ideal is the minimum for all ideals that can be constructed from P. We call this problem the minimum-weight x-ideal problem. In this paper we explore a further possibility for a solvable case of this problem because it has been proven that this problem is NP-hard even if the Hasse diagram representing a given poset is a bipartite graph. We obtain two new results. First, we describe an O(K2n) algorithm on the special poset whose Hasse diagram is a directed tree, which is called a directed tree poset. Here n is the cardinality of the underlying set of the given poset. This outperforms an O(n4) algorithm that is the best previously known. Secondly, we show a characteristic of the polyhedron obtained from the LP-relaxation of the K-ideal problem on a directed tree poset. This is the first step to solve the other type K-ideal problems from the LP-relaxation technique.","subitem_description_type":"Abstract"}]},"item_5_description_38":{"attribute_name":"フォーマット","attribute_value_mlt":[{"subitem_description":"application/pdf","subitem_description_type":"Other"}]},"item_5_source_id_19":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"03893367"}]},"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":"BKSJ170015"}]},"item_5_text_8":{"attribute_name":"所属機関","attribute_value_mlt":[{"subitem_text_value":"文教大学情報学部"}]},"item_5_text_9":{"attribute_name":"Institution","attribute_value_mlt":[{"subitem_text_value":"Bunkyo University Faculty of Information and Communications"}]},"item_5_version_type_35":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Nemoto,Toshio"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-03-24"}],"displaytype":"detail","filename":"BKSJ170015.pdf","filesize":[{"value":"524.1 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"BKSJ170015.pdf","url":"https://bunkyo.repo.nii.ac.jp/record/3450/files/BKSJ170015.pdf"},"version_id":"9ebd94f4-c79d-4690-ad28-9e4bda7c6d0a"}]},"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":"The Minimum-weight k-Ideal Problem on a Directed Tree Poset and Its Polyhedron","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"The Minimum-weight k-Ideal Problem on a Directed Tree Poset and Its Polyhedron"}]},"item_type_id":"5","owner":"3","path":["201"],"pubdate":{"attribute_name":"公開日","attribute_value":"2012-01-17"},"publish_date":"2012-01-17","publish_status":"0","recid":"3450","relation_version_is_last":true,"title":["The Minimum-weight k-Ideal Problem on a Directed Tree Poset and Its Polyhedron"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2023-05-16T14:20:36.179359+00:00"}