Non-submodular maximization with a decomposable objective function

DOI10.1007/S10878-024-01224-9MaRDI QIDQ7031274zbMATH OpenFDO

Authors Cheng Lu, Wenguo Yang

Publication date 6 February 2025

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-024-01224-9

zbMATH Keywords

difference of set functionsgreedy algorithmnon-submodular optimizationratio of set functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Cites work

• A tight analysis of the submodular-supermodular procedure
• Combinatorial auctions with decreasing marginal utilities
• Guess free maximization of submodular and linear sums
• Minimizing ratio of monotone non-submodular functions
• Optimal approximation for submodular and supermodular optimization with bounded curvature
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The Concave-Convex Procedure

Cited in

(1)

• Optimization of regional economic resources combined with artificial intelligence technology and multi-factor analysis in belt and road environment

This page was built for publication: Non-submodular maximization with a decomposable objective function

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