WEKO3
インデックスリンク
アイテム
Algorithms for the Minimax k-Ideal Problem
https://bunkyo.repo.nii.ac.jp/records/3457
https://bunkyo.repo.nii.ac.jp/records/345732a5154f-7f66-407b-b24b-97f753761b90
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
BKSJ180007.pdf (641.0 kB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-01-17 | |||||||
| タイトル | ||||||||
| タイトル | Algorithms for the Minimax k-Ideal Problem | |||||||
| 言語 | ||||||||
| 言語 | 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(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. | |||||||
| 書誌情報 |
情報研究 en : Information and Communication Studies 巻 18, p. 135-147, 発行日 1997-01-01 |
|||||||
| 出版者 | ||||||||
| 出版者 | 文教大学 | |||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 03893367 | |||||||
| 著者版フラグ | ||||||||
| 出版タイプ | VoR | |||||||
| 本文言語 | ||||||||
| 値 | 英語 | |||||||
| ID | ||||||||
| 値 | BKSJ180007 | |||||||
