Bicriteria streaming algorithms to balance gain and cost with cardinality constraint
Author
Abstract
Suggested Citation
DOI: 10.1007/s10878-021-00827-w
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Maxim Sviridenko & Jan Vondrák & Justin Ward, 2017. "Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 1197-1218, November.
- Yijing Wang & Dachuan Xu & Yishui Wang & Dongmei Zhang, 2020. "Non-submodular maximization on massive data streams," Journal of Global Optimization, Springer, vol. 76(4), pages 729-743, April.
- Suning Gong & Qingqin Nong & Wenjing Liu & Qizhi Fang, 2019. "Parametric monotone function maximization with matroid constraints," Journal of Global Optimization, Springer, vol. 75(3), pages 833-849, November.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Bin Liu & Miaomiao Hu, 2022. "Fast algorithms for maximizing monotone nonsubmodular functions," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1655-1670, July.
- Cheng Lu & Wenguo Yang & Ruiqi Yang & Suixiang Gao, 2022. "Maximizing a non-decreasing non-submodular function subject to various types of constraints," Journal of Global Optimization, Springer, vol. 83(4), pages 727-751, August.
- Zhicheng Liu & Longkun Guo & Donglei Du & Dachuan Xu & Xiaoyan Zhang, 2022. "Maximization problems of balancing submodular relevance and supermodular diversity," Journal of Global Optimization, Springer, vol. 82(1), pages 179-194, January.
- Zhenning Zhang & Bin Liu & Yishui Wang & Dachuan Xu & Dongmei Zhang, 2022. "Maximizing a monotone non-submodular function under a knapsack constraint," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1125-1148, July.
- Zhenning Zhang & Donglei Du & Yanjun Jiang & Chenchen Wu, 2021. "Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint," Journal of Global Optimization, Springer, vol. 80(3), pages 595-616, July.
- Xiaojuan Zhang & Qian Liu & Min Li & Yang Zhou, 2022. "Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3549-3574, December.
- Shaojie Tang & Jing Yuan, 2023. "Beyond submodularity: a unified framework of randomized set selection with group fairness constraints," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-22, May.
- Fernando, Garcia Alvarado & Antoine, Mandel, 2022.
"The network structure of global tax evasion evidence from the Panama papers,"
Journal of Economic Behavior & Organization, Elsevier, vol. 197(C), pages 660-684.
- Garcia Alvarado Fernando & Mandel Antoine, 2022. "The network structure of global tax evasion Evidence from the Panama Papers," Post-Print hal-03881348, HAL.
- Garcia Alvarado Fernando & Mandel Antoine, 2022. "The network structure of global tax evasion Evidence from the Panama Papers," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-03881348, HAL.
- Ruiqi Yang & Dachuan Xu & Longkun Guo & Dongmei Zhang, 2021. "Sequence submodular maximization meets streaming," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 43-55, January.
- Sekar, Shreyas & Vojnovic, Milan & Yun, Se-Young, 2020. "A test score based approach to stochastic submodular optimization," LSE Research Online Documents on Economics 103176, London School of Economics and Political Science, LSE Library.
- Majun Shi & Zishen Yang & Wei Wang, 2023. "Greedy Guarantees for Non-submodular Function Maximization Under Independent System Constraint with Applications," Journal of Optimization Theory and Applications, Springer, vol. 196(2), pages 516-543, February.
- Jingjing Tan & Yicheng Xu & Dongmei Zhang & Xiaoqing Zhang, 2023. "On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice," Journal of Combinatorial Optimization, Springer, vol. 45(2), pages 1-19, March.
- Cheng Lu & Wenguo Yang, 2024. "Fast deterministic algorithms for non-submodular maximization with strong performance guarantees," Journal of Global Optimization, Springer, vol. 89(3), pages 777-801, July.
- Shreyas Sekar & Milan Vojnovic & Se-Young Yun, 2021. "A Test Score-Based Approach to Stochastic Submodular Optimization," Management Science, INFORMS, vol. 67(2), pages 1075-1092, February.
- Min Cui & Dachuan Xu & Longkun Guo & Dan Wu, 2022. "Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1671-1690, July.
- Cheng Lu & Wenguo Yang & Suixiang Gao, 2022. "A new greedy strategy for maximizing monotone submodular function under a cardinality constraint," Journal of Global Optimization, Springer, vol. 83(2), pages 235-247, June.
- Shufang Gong & Bin Liu & Mengxue Geng & Qizhi Fang, 2023. "Algorithms for maximizing monotone submodular function minus modular function under noise," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-18, May.
- Min Cui & Donglei Du & Dachuan Xu & Ruiqi Yang, 2023. "Two approximation algorithms for maximizing nonnegative weakly monotonic set functions," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-18, January.
- Bin Liu & Zihan Chen & Huijuan Wang & Weili Wu, 2023. "An optimal streaming algorithm for non-submodular functions maximization on the integer lattice," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-17, January.
More about this item
Keywords
Streaming algorithm; Approximately submodular; Linear function; Bicriteria;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00827-w. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.