Quantcast

Faster approximation algorithms for maximizing a monotone submodular function subject to a b-matching constraint

Research paper by Kaito Fujii

Indexed on: 09 Apr '16Published on: 08 Apr '16Published in: Information Processing Letters



Abstract

Maximizing a monotone submodular function subject to a b  -matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other than the greedy algorithm. The best approximation scheme so far is the local search algorithm, proposed by Feldman, Naor, Schwartz, and Ward (2011). It obtains a <img height="19" border="0" style="vertical-align:bottom" width="84" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0020019016300461-si1.gif">1/(2+1k+ϵ)-approximate solution for an arbitrary positive integer k and positive real number ϵ. For graphs with n vertices and m   edges, the running time of the local search algorithm is O(bk+1(Δ−1)knmϵ−1)O(bk+1(Δ−1)knmϵ−1) where Δ is the maximum degree, which is impractical for large problems. In this paper, we present two new algorithms for this problem. One is a find walk algorithm that runs in O(bm)O(bm) time and achieves 1/4-approximation. It is faster than the greedy algorithm whose approximation ratio is 1/3. The other one is a randomized local search algorithm that is a faster variant of the local search algorithm. In expectation, it runs in <img height="19" border="0" style="vertical-align:bottom" width="158" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0020019016300461-si115.gif">O(bk+1(Δ−1)k−1mlog⁡1ϵ) time and obtains a <img height="19" border="0" style="vertical-align:bottom" width="95" alt="View the MathML source" title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0020019016300461-si114.gif">(1/(2+1k)−ϵ)-approximate solution.

Figure 10.1016/j.ipl.2016.04.004.0.gif
Figure 10.1016/j.ipl.2016.04.004.1.gif
Figure 10.1016/j.ipl.2016.04.004.2.gif
Figure 10.1016/j.ipl.2016.04.004.3.gif
Figure 10.1016/j.ipl.2016.04.004.4.gif