Minimization problems with non-submodular cover constraint

DOI10.1142/S0217595923400122MaRDI QIDQ6542984zbMATH OpenFDO

Authors Wen-qi Wang, Zhicheng Liu, Donglei Du, Peihao Shi, Xiaoyan Zhang

Publication date 23 May 2024

Published in Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0217595923400122

zbMATH Keywords

approximation algorithmcombinatorial optimizationgreedy algorithmprimal-dual algorithmsubmodular function

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Minimum non-submodular cover problem with applications
• Submodular function minimization under a submodular set covering constraint
• Submodular function minimization with submodular set covering constraints and precedence constraints
• On minimum submodular cover with submodular cost
• Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A Greedy Heuristic for the Set-Covering Problem
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• An analysis of the greedy algorithm for the submodular set covering problem
• Analytical approach to parallel repetition
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• Approximation algorithms for combinatorial problems
• Discrete convex analysis
• Geometric algorithms and combinatorial optimization.
• Graph cuts with interacting edge weights: examples, approximations, and algorithms
• Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Minimum non-submodular cover problem with applications
• On the ratio of optimal integral and fractional covers
• Primal-dual algorithms for precedence constrained covering problems
• Reducibility among combinatorial problems
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Submodular function minimization under a submodular set covering constraint
• Submodular Function Minimization under Covering Constraints
• Submodular function minimization with submodular set covering constraints and precedence constraints
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(1)

• Approximate Submodularity in Network Design Problems

This page was built for publication: Minimization problems with non-submodular cover constraint

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