Submodular Function Maximization on the Bounded Integer Lattice

DOI10.1007/978-3-319-28684-6_12zbMath1479.90174OpenAlexW2121293983MaRDI QIDQ2788997

Corinna Gottschalk, Britta Peis

Publication date: 26 February 2016

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-28684-6_12

zbMATH Keywords

deterministic \(\frac{1}{3}\)-approximation, submodular set function

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --, A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice, A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity, A binary search double greedy algorithm for non-monotone DR-submodular maximization, A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function, Profit maximization in social networks and non-monotone DR-submodular maximization, A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions, Robust budget allocation via continuous submodular functions, Monotone submodular maximization over the bounded integer lattice with cardinality constraints, Maximizing monotone submodular functions over the integer lattice, A fast double greedy algorithm for non-monotone DR-submodular function maximization, Rank axiom of modular supermatroids: a connection with directional DR submodular functions