A fast double greedy algorithm for non-monotone DR-submodular function maximization

DOI10.1142/S179383092050007XMaRDI QIDQ5216445zbMATH OpenOpenAlexWikidataFDO

Authors Shuyang Gu, Ganquan Shi, Weili Wu, Changhong Lu

Publication date 18 February 2020

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s179383092050007x

zbMATH Keywords

bounded integer latticedouble greedyDR-submodularunconstrained submodular maximization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• 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
• A survey on double greedy algorithms for maximizing non-monotone submodular functions
• Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
• Profit maximization in social networks and non-monotone DR-submodular maximization

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Deterministic Algorithms for Submodular Maximization Problems
• Fast algorithms for maximizing submodular functions
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing Non-monotone Submodular Functions
• Submodular function maximization on the bounded integer lattice
• Submodular maximization by simulated annealing
• Submodular maximization with cardinality constraints
• Substitute goods, auctions, and equilibrium

Cited in

(11)

• On strict submodularity of social influence
• Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint
• A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
• Profit maximization in social networks and non-monotone DR-submodular maximization
• Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization
• A survey on double greedy algorithms for maximizing non-monotone submodular functions
• scientific article; zbMATH DE number 7255156 (Why is no real title available?)
• A binary search double greedy algorithm for non-monotone DR-submodular maximization
• Online non-monotone diminishing return submodular maximization in the bandit setting
• Dynamic algorithms for maximizing a DR-submodular function subtracted by a linear function over the integer lattice
• A short proof for stronger version of DS decomposition in set function optimization

This page was built for publication: A fast double greedy algorithm for non-monotone DR-submodular function maximization

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