Efficient deterministic algorithms for maximizing symmetric submodular functions

DOI10.1016/J.TCS.2025.115312MaRDI QIDQ6971743zbMATH OpenFDO

Authors Zongqi Wan, Jialin Zhang, Xiaoming Sun, Zhi-Jie Zhang

Publication date 13 June 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115312

zbMATH Keywords

approximation algorithmdeterministic algorithmsymmetric submodular maximization

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A simple deterministic algorithm for symmetric submodular maximization subject to a knapsack constraint
• A Unified Continuous Greedy Algorithm for Submodular Maximization
• Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Better balance by being biased: a 0.8776-approximation for {\textsc{Max Bisection}}
• Canonical decompositions of symmetric submodular systems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Comparing apples and oranges: query tradeoff in submodular maximization
• Constrained submodular maximization via a nonsymmetric technique
• Constrained submodular maximization: beyond 1/e
• Deterministic Algorithms for Submodular Maximization Problems
• Efficient Submodular Function Maximization under Linear Packing Constraints
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• scientific article; zbMATH DE number 7788402 (Why is no real title available?)
• Improved deterministic algorithms for non-monotone submodular maximization
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing Non-monotone Submodular Functions
• Maximizing symmetric submodular functions
• Minimizing symmetric submodular functions
• Non-monotone submodular maximization under matroid and knapsack constraints
• On maximizing sums of non-monotone submodular and linear functions
• Optimal approximation for the submodular welfare problem in the value oracle model
• Submodular maximization by simulated annealing
• Submodular maximization with cardinality constraints
• The budgeted maximum coverage problem

This page was built for publication: Efficient deterministic algorithms for maximizing symmetric submodular functions

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