Search

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k2+1 2k2+1 -approximation for k geq 3. We also give a randomized surd 17 3 2 -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and v Zivn'y [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities. [ABSTRACT FROM AUTHOR]

We consider approximation algorithms for packing integer programs (PIPs) of the form max { ⟨ c , x ⟩ : A x ≤ b , x ∈ { 0 , 1 } n } where A, b and c are nonnegative. We let W = min i , j b i / A i , j denote the width of A which is at least 1. Previous work by Bansal et al. (Theory Comput 8(24):533–565, 2012) obtained an Ω (1 Δ 0 1 / ⌊ W ⌋ ) -approximation ratio where Δ 0 is the maximum number of nonzeroes in any column of A (in other words the ℓ 0 -column sparsity of A). They raised the question of obtaining approximation ratios based on the ℓ 1 -column sparsity of A (denoted by Δ 1 ) which can be much smaller than Δ 0 . Motivated by recent work on covering integer programs (Chekuri and Quanrud, in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1596–1615. SIAM, 2019; Chen et al., in: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1984–2003. SIAM, 2016) we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. (Theory Comput 8(24):533–565, 2012) (but with a twist), yield approximation ratios for PIPs based on Δ 1 . First, following an integrality gap example from (Theory Comput 8(24):533–565, 2012), we observe that the case of W = 1 is as hard as maximum independent set even when Δ 1 ≤ 2 . In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width W = 1 + ϵ where ϵ ∈ (0 , 1 ] , we obtain an Ω (ϵ 2 / Δ 1) -approximation. In the large width regime, when W ≥ 2 , we obtain an Ω ((1 1 + Δ 1 / W) 1 / (W - 1)) -approximation. We also obtain a (1 - ϵ) -approximation when W = Ω (log (Δ 1 / ϵ) ϵ 2) . Viewing the rounding algorithms as contention resolution schemes, we obtain approximation algorithms in the more general setting when the objective is a non-negative submodular function. [ABSTRACT FROM AUTHOR]