Minimization problems with non-submodular cover constraint
From MaRDI portal
Publication:6542984
DOI10.1142/s0217595923400122zbMATH Open1547.90173MaRDI QIDQ6542984
Zhi-cheng Liu, Wen-qi Wang, Peihao Shi, Xiaoyan Zhang, Dong-lei Du
Publication date: 23 May 2024
Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)
combinatorial optimizationapproximation algorithmgreedy algorithmsubmodular functionprimal-dual algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- The ellipsoid method and its consequences in combinatorial optimization
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Discrete convex analysis
- Geometric algorithms and combinatorial optimization.
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- Submodular function minimization with submodular set covering constraints and precedence constraints
- An analysis of the greedy algorithm for the submodular set covering problem
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- Minimum non-submodular cover problem with applications
- Primal-dual algorithms for precedence constrained covering problems
- Submodular Function Minimization under a Submodular Set Covering Constraint
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- A Greedy Heuristic for the Set-Covering Problem
- Reducibility among Combinatorial Problems
- Submodular Function Minimization under Covering Constraints
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Analytical approach to parallel repetition
This page was built for publication: Minimization problems with non-submodular cover constraint
