Monotone submodular maximization under the pairwise capacity constraint

DOI10.1007/S10898-025-01576-4MaRDI QIDQ6851190zbMATH OpenFDO

Authors Yuanyuan Qiang, Bin Liu, Weili Wu

Publication date 27 February 2026

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

Full work available at URL https://doi.org/10.1007/S10898-025-01576-4

zbMATH Keywords

approximation algorithmknapsack constraintstreaming algorithmsubmodular maximization

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• An analysis of approximations for maximizing submodular set functions—I
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Group equality in adaptive submodular maximization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Local search algorithm for universal facility location problem with linear penalties
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximizing a monotone submodular function subject to a matroid constraint
• Streaming submodular maximization under matroid constraints
• Submodular maximization by simulated annealing
• Submodular maximization meets streaming: matchings, matroids, and more
• The one-way communication complexity of submodular maximization with applications to streaming and robustness

This page was built for publication: Monotone submodular maximization under the pairwise capacity constraint

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