Approximation algorithm of maximizing non-submodular functions under non-submodular constraint

DOI10.1016/j.dam.2024.09.022MaRDI QIDQ6657221

Yishuo Shi, Xiaoyan Lai

Publication date: 6 January 2025

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

greedy algorithmnon-monotonenon-submodularnon-submodular constraint

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Mathematical programming (90Cxx) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• An \(R\)-square coefficient based on final prediction error
• Seven proofs for the subadditivity of expected shortfall
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• Maximizing monotone submodular functions over the integer lattice
• Two approximation algorithms for maximizing nonnegative weakly monotonic set functions
• A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice
• Bicriteria algorithms to balance coverage and cost in team formation under online model
• Greedy guarantees for non-submodular function maximization under independent system constraint with applications
• Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Some optimal inapproximability results
• Weakly Submodular Function Maximization Using Local Submodularity Ratio.
• Approximation algorithm of maximizing non-monotone non-submodular functions under knapsack constraint

This page was built for publication: Approximation algorithm of maximizing non-submodular functions under non-submodular constraint