Abstract
We consider the problem of maximizing a submodular function on the bounded integer lattice. As a direct generalization of submodular set functions, \(f: \{0, \ldots , C\}^n \rightarrow \mathbb {R}_+\) is submodular, if \(f(x) + f(y) \ge f(x \wedge y) + f(x \vee y)\) for all \(x,y \in \{0, \ldots , C\}^n\) where \(\wedge \) and \(\vee \) denote element-wise minimum and maximum. The objective is finding a vector x maximizing f(x). In this paper, we present a deterministic \(\frac{1}{3}\)-approximation using a framework inspired by [2]. We also provide an example that shows the analysis is tight and yields additional insight into the possibilities of modifying the algorithm. Moreover, we examine some structural differences to maximization of submodular set functions which make our problem harder to solve.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bolandnazar, M., Huh, W., McCormick, S., Murota, K.: A note on “order-based cost optimization in assemble-to-order systems”. University of Tokyo (February, Techical report (2015)
Buchbinder, N., Feldmann, M., Naor, J., Schwartz, R.: A tight linear (1/2)-approximation for unconstrained submodular maximization. In: FOCS pp. 649–658 (2012)
Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. CoRR (2015). abs/1505.02695
Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 182–196. Springer, Heidelberg (2007)
Feige, M.: Vondrák: Maximizing Non-Monotone Submodular Functions. SIAM Journal on Computing 40(4), 1133–1153 (2011)
Feldman, M., Naor, J.S., Schwartz, R.: Nonmonotone submodular maximization via a structural continuous greedy algorithm. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 342–353. Springer, Heidelberg (2011)
Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics, vol. 58, 2nd edn, pp. 305–308. Elsevier, New York (2005)
Goldengorin, B., Tijssen, G., Tso, M.: The maximization of submodular functions: old and new proofs for the correctness of the dichotomy algorithm. Technical report 99A17, University of Groningenm Research Institute SOM (1999)
Golovin, D., Krause, A.: Submodular function maximization. In: Bordeaux, L., Hamadi, Y., Kohli, P. (eds.) Tractability: Practical Approaches to Hard Problems. Cambridge University Press, Cambridge (2014)
Grabisch, M., Xie, L.: The restricted core of games on distributive lattices: how to share benefits in a hierarchy. Math. Methods Oper. Res. 73, 189–208 (2011)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)
Inaba, K., Kakimura, N., K., K., Soma, T.: Optimal budget allocation: Theoretical guarantee and efficient algorithm. In: Proceedings of the 31st International Conference on Machine Learning, pp. 351–359 (2014). JMLR.org
Murota, K.: Submodular function minimization and maximization in discrete convex analysis. RIMS Kokyuroku Bessatsu B23, 193–211 (2010)
Oveis Gharan, S., Vondrák, J.: Submodular maximization by simulated annealing. In: SODA, pp. 1098–1117 (2011)
Schulz, A., Uhan, N.: Approximating the least core value and least core of cooperative games with supermodular costs. Discrete Optim. 10(2), 163–180 (2013)
Soma, T., Yoshida, Y.: Maximizing submodular functions with the diminishing return property over the integer lattice. CoRR 2015. abs/1503.01218
Acknowledgement
We thank S.Thomas McCormick and Kazuo Murota for fruitful discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Gottschalk, C., Peis, B. (2015). Submodular Function Maximization on the Bounded Integer Lattice. In: Sanità, L., Skutella, M. (eds) Approximation and Online Algorithms. WAOA 2015. Lecture Notes in Computer Science(), vol 9499. Springer, Cham. https://doi.org/10.1007/978-3-319-28684-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-28684-6_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-28683-9
Online ISBN: 978-3-319-28684-6
eBook Packages: Computer ScienceComputer Science (R0)