Approximation Algorithms for Non-Submodular Optimization Over Sliding Windows

Yunxin Luo (), Chenchen Wu () and Chunming Xu
Additional contact information
Yunxin Luo: Institute of Operations Research and Systems Engineering, College of Science, Tianjin, University of Technology, Tianjin 300384, P. R. China
Chenchen Wu: Institute of Operations Research and Systems Engineering, College of Science, Tianjin, University of Technology, Tianjin 300384, P. R. China
Chunming Xu: Institute of Operations Research and Systems Engineering, College of Science, Tianjin, University of Technology, Tianjin 300384, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2022, vol. 39, issue 05, 1-20

Abstract: In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window model. Based on the concept of diminishing-return ratio γ, we propose a (1 3γ2 − 𠜀)-approximation algorithm with the memory O(klog2(kΦ 1 γ) 𠜀2), where Φ is the ratio between maximum and minimum values of any singleton element of function f. Then, we improve the approximation ratio to (1 2γ − 𠜀) through the sub-windows at the expense of losing some memory. Our results generalize the corresponding results for the submodular case.

Keywords: Streaming algorithm; non-submodular maximization; cardinality constraint; set function; sliding window (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S021759592150038X
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:39:y:2022:i:05:n:s021759592150038x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S021759592150038X

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 ().