劣モジュラ, 正モジュラ集合関数の多重グラフによる増大法

17 References

Bibliographic Information

Other Title
  • Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Search this article

Description

有限集合 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.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 66 41-48, 1999-01-27

    Information Processing Society of Japan (IPSJ)

References(17)*help

See more

Details 詳細情報について

  • CRID
    1573668926953559040
  • NII Article ID
    110002812347
  • NII Book ID
    AN1009593X
  • ISSN
    09196072
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top