Approximating Submodular Functions


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.


Source Codes in J2SE

References
[1] M. X. Goemans, N.J. Harvey, S. Iwata, and V. Mirrokni, Approximating Submodular Functions Everywhere, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp.535-544.
SODA 2009 Proceedings
[2] H. Okano, On submodular function approximation algorithms (in Japanese), Master Thesis, University of Tokyo, 2010.


DCP Project
Naonori KAKIMURA (kakimura(a)math.keio.ac.jp) Replace '(a)' with '@'
modified on Apr. 2016.