WEKO3
インデックスリンク
アイテム
The Minimum-weight k-Ideal Problem on a Directed Tree Poset and Its Polyhedron
https://bunkyo.repo.nii.ac.jp/records/3450
https://bunkyo.repo.nii.ac.jp/records/3450ae84bf40-425c-45db-b3eb-c5949cec6af0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
BKSJ170015.pdf (524.1 kB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-01-17 | |||||||
| タイトル | ||||||||
| タイトル | The Minimum-weight k-Ideal Problem on a Directed Tree Poset and Its Polyhedron | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ | departmental bulletin paper | |||||||
| 著者 |
Nemoto,Toshio
× Nemoto,Toshio
|
|||||||
| 所属機関 | ||||||||
| 値 | 文教大学情報学部 | |||||||
| 内容記述 | ||||||||
| 内容記述タイプ | Abstract | |||||||
| 内容記述 | 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. | |||||||
| 書誌情報 |
情報研究 en : Information and Communication Studies 巻 17, p. 265-274, 発行日 1996-01-01 |
|||||||
| 出版者 | ||||||||
| 出版者 | 文教大学 | |||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 03893367 | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 本文言語 | ||||||||
| 値 | 英語 | |||||||
| ID | ||||||||
| 値 | BKSJ170015 | |||||||
