Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions

DOI10.1007/s11590-023-01979-wOpenAlexW4321600307MaRDI QIDQ6164960

Wenguo Yang, Cheng Lu, Sui-Xiang Gao

Publication date: 28 July 2023

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-023-01979-w

zbMATH Keywords

curvaturestreaming algorithmdifference of submodular functionsnonsubmodular maximizationsum of submodular and supermodular functions

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• PASS approximation: a framework for analyzing and designing heuristics
• Maximize a monotone function with a generic submodularity ratio
• Online algorithms for BP functions maximization
• Non-submodular maximization on massive data streams
• A tight analysis of the submodular-supermodular procedure
• Combinatorial auctions with decreasing marginal utilities
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• The Concave-Convex Procedure
• Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature
• Online Submodular Maximization with Preemption
• Guess free maximization of submodular and linear sums
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions