We consider the following problem:
Given a monotone submodular function f on E,
construct using polynomially many oracle queries a function g such that g (X)≤ f(X) ≤ α(n) g(X) for any X⊆ E.
The source code below, written by Hiroki Okano in 2009, implements the
algorithm by Goemans, Harvey, Iwata, and Mirrokni[1].
This algorithm returns a function g with α(n)=O(sqrt(n)log n) in polynomial number of queries.
Please check README file in the tar file before using the programs.
DCP Project | Naonori KAKIMURA (kakimura(a)math.keio.ac.jp) Replace '(a)' with '@' modified on Apr. 2016. |