劣モジュラ, 正モジュラ集合関数の多重グラフによる増大法
書誌事項
- タイトル別名
-
- Augmenting a Submodular and Posi-modular Set Function by a Multigraph
この論文をさがす
説明
有限集合 V と集合関数 ƒ : 2^V & Z (Zは整数値の集合) が与えれたとき, V上で多重グラフ G=(V, E) を構成し, G のカット関数 c_Gが任意の非空部分集合 X⊂V に対してƒ(X)+c_G(X)≥2を満たすようにする. 関数 f が交差劣モジュラ, 正モジュラであり, かつ三部不等式を満たすとき, 上記の性質を満たすグラフの中で辺数最小のものをO((T_ƒ+1)n^4log n) 時間で求めるアルゴリズムを与える. ここで, n=|V|, T_ƒ与えられたX⊂Vに対しƒ(X)の値を返す時間とする.
Given a finite set V and a set function ƒ : 2^V → Z (Z is the set of integers), we consider the problem of constructing an undirected multigraph G = (V, E) such that the cut function c_G of G satisfies ƒ(X)+c_G(X) ≥ 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in O((T_ƒ+1)n^4logn) time, where n=|V| and T_ƒ is the time to compute the value of ƒ(X) for a subset X⊂V.
収録刊行物
-
- 情報処理学会研究報告. AL, アルゴリズム研究会報告
-
情報処理学会研究報告. AL, アルゴリズム研究会報告 66 41-48, 1999-01-27
一般社団法人情報処理学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1573668926953559040
-
- NII論文ID
- 110002812347
-
- NII書誌ID
- AN1009593X
-
- ISSN
- 09196072
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles