ラミナー被覆制約を持つ単調凹関数最小化問題

• Item type: SIG Technical Reports(1)
• 公開日: 2004-01-30
• タイトル: ラミナー被覆制約を持つ単調凹関数最小化問題
• タイトル / 言語: en
• タイトル: Minimizing a Monotone Concave Function with Laminar Covering Constraints
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院基礎工学研究科社会システム数理領域
• 著者所属: 大阪大学大学院基礎工学研究科社会システム数理領域
• 著者所属: 京都大学数理解析研究所
• 著者所属(英): en
• 著者所属(英): Division of Mathematical Science for Social Systems, Graduate School of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Division of Mathematical Science for Social Systems, Graduate School of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Research Institute for Mathematical Sciences, Kyoto University
• 著者名: 坂下, 麻里子; 牧野, 和久; 藤重, 悟
• 著者名(英): Mariko, Sakashita; Makino, Kazuhisa; Satoru, Fujishige
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Vを|V|=nである有限の集合とする．Vの部分集合族 F⊆2^Vは，任意の集合X Y∈Fに対して，X∩Y=Φ，X⊆Y，X⊇Yのいずれかが成立するとき，ラミナー族と呼ばれる．本研究では，ラミナー族 F，ラミナー族上の要求関数 d，コストを表す単調凹関数fが与えられたとき，ラミナー被覆制約と非負制約を満たしながらコストf(x)を最小化する問題を考察する．本研究では，コスト関数fがラミナー族Fに基づくVの分割上の単調凹関数に分離できるとき，上記の問題がO(n^2 q) 時間で解けることを示す．ただし，qはxからf(x)を得るための計算量である．また，fがオラクルとして与えられるときはΩ(n^2 q) 時間必要であり，このときには我々の提案するアルゴリズムが最適であることを示す．さらにfが固定費つきの線形関数fv(v∈V)の和として表現できる場合に対するO(nlog^2 n) 時間アルゴリズムを構成する．一般の単調凹関数fに対しては，Fがオラクルとして与えられるならば，Ω(2^{n/2}q) 時間必要であり，fが明示的に与えられる場合でもNP困難であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let V be a finite set with V=n. A family F⊆2^V is called laminar if for all two sets X,Y∈F, X∩Y≠Φ implies X⊆Y or X⊇Y. Given a laminar family F, a nonnegative demand function d and a monotone concave cost function f, we consider the problem of finding a minimum-cost x such that x(X)≧d(X) for all X∈F. In this paper, we show that the problem can be solved in O(n^2 q) time, if f can be decomposed into monotone concave functions by the partition of V based on F where q is the time needed to compute f(x) for any x. We also prove that if f is given as an oracle then it takes Ω(n^2 q) time to solve the problem. This implies that the algorithm proposed in this paper is optimal. We give an O(nlog^2 n) algorithm if f is the sum of linear cost functions with fixed opening costs. Finally, we show that in general our problem needs Ω(2^{n/2}q) when f is given as an oracle, and it is NP-hard, if f is given explicitly.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2004, 号 10(2003-AL-093), p. 17-24, 発行日 2004-01-30
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会