Submodular function maximization on the bounded integer lattice

DOI10.1007/978-3-319-28684-6_12MaRDI QIDQ2788997zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Monotone submodular maximization over the bounded integer lattice with cardinality constraints
• A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
• A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function

Cited in

(17)

• Robust budget allocation via continuous submodular functions
• Rank axiom of modular supermatroids: a connection with directional DR submodular functions
• 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 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
• Monotone submodular maximization over the bounded integer lattice with cardinality constraints
• A fast double greedy algorithm for non-monotone DR-submodular function maximization
• 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
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Regularized submodular maximization over integer lattice
• Fast approximation algorithm for non-monotone DR-submodular maximization under size constraint
• Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
• Maximizing the ratio of monotone DR-submodular functions on integer lattice
• Dynamic algorithms for maximizing a DR-submodular function subtracted by a linear function over the integer lattice

This page was built for publication: Submodular function maximization on the bounded integer lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2788997)