Minimization Problems with Non-Submodular Cover Constraint

Wenqi Wang (), Zhicheng Liu (), Donglei Du (), Peihao Shi () and Xiaoyan Zhang
Additional contact information
Wenqi Wang: School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing 210023, P. R. China
Zhicheng Liu: Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, P. R. China
Donglei Du: Faculty of Management, University of New Brunswick, Fredericton, New Brunswick, Canada E3B9Y2, Canada
Peihao Shi: Nanjing Kinghua Operations Research and Artificial Intelligence, Industrial Technology Research Institute Co., Ltd., Nanjing 210035, P. R. China
Xiaoyan Zhang: School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing 210023, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 05, 1-19

Abstract: The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lovász extension, we devise greedy and primal–dual approximation algorithms for these problems.

Keywords: Approximation algorithm; submodular function; combinatorial optimization; greedy algorithm; primal–dual algorithm (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595923400122
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:05:n:s0217595923400122

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595923400122

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().