Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexity

• Amanatidis G, Fusco F, Lazos P, Leonardi S, Marchetti-Spaccamela A, Reiffenhäuser R (2021) Submodular maximization subject to a knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity. In: International conference on machine learning, proceedings of machine learning research, 139:231–242

• Amanatidis G, Fusco F, Lazos P, Leonardi S, Reiffenhäuser R (2020) Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In: Annual conference on neural information processing systems

• Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. In: Annual ACM-SIAM symposium on discrete algorithms, pp. 1497–1514. https://doi.org/10.1137/1.9781611973402.110

• Buchbinder N, Feldman M (2019) Constrained submodular maximization via a nonsymmetric technique. Math Oper Res 44(3):988–1005

  Article  MathSciNet  Google Scholar 

• Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J Comput 43(6):1831–1879

  Article  MathSciNet  Google Scholar 

• Chen Y, Kuhnle A (2023) Approximation algorithms for size-constrained non-monotone submodular maximization in deterministic linear time. In: A.K. Singh, Y. Sun, L. Akoglu, D. Gunopulos, X. Yan, R. Kumar, F. Ozcan, J. Ye (eds.) Proceedings of the 29th ACM SIGKDD conference on knowledge discovery and data mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pp. 250–261. ACM

• Cui S, Han K, Tang J, Huang H, Li X, Li Z (2021) Streaming algorithms for constrained submodular maximization. Proc ACM Meas Anal Comput Syst 6(3):54:1-54:32

  Google Scholar 

• Ene A, Nguyen HL (2019) A nearly-linear time algorithm for submodular maximization with a knapsack constraint. Int Colloq Autom Lang Programm 132:53:1-53:12

  MathSciNet  Google Scholar 

• Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. In: Annual symposium on foundations of computer science, pp. 570–579

• Gupta A, Roth A, Schoenebeck G, Talwar K (2010) Constrained non-monotone submodular maximization: offline and secretary algorithms. In: International workshop on internet and network economics

• Ha DTK, Pham CV, Tran TD (2024) Improved approximation algorithms for k-submodular maximization under a knapsack constraint. Comput Oper Res 161:106452. https://doi.org/10.1016/j.cor.2023.106452

  Article  MathSciNet  Google Scholar 

• Han K, Cui S, Zhu T, Zhang E, Wu B, Yin Z, Xu T, Tang S, Huang H (2021) Approximation algorithms for submodular data summarization with a knapsack constraint. Proc ACM Meas Anal Comput Syst 5(1):05:1-05:31

  Article  Google Scholar 

• Kuhnle A (2019) Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. In: Neural information processing systems, pp. 2371–2381

• Kulik A, Shachnai H, Tamir T (2013) Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math Oper Res 38(4):729–739

  Article  MathSciNet  Google Scholar 

• Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2010) Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J Discret Math 23(4):2053–2078

  Article  MathSciNet  Google Scholar 

• Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2010) Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J Discret Math 23(4):2053–2078

  Article  MathSciNet  Google Scholar 

• Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen JM, Glance NS (2007) Cost-effective outbreak detection in networks. In: Proc. of the 13th ACM SIGKDD Conf., 2007, pp. 420–429

• Li W (2018) Nearly linear time algorithms and lower bound for submodular maximization. preprint, arXiv:1804.08178

• Li W, Feldman M, Kazemi E, Karbasi A (2022) Submodular maximization in clean linear time. In: Advances in neural information processing systems, pp. 7887–7897

• Mirzasoleiman B, Badanidiyuru A, Karbasi A (2016) Fast constrained submodular maximization: Personalized data summarization. In: International conference on machine learning, JMLR Workshop and Conf. Proc., vol. 48, pp. 1358–1367

• Mirzasoleiman B, Karbasi A, Badanidiyuru A, Krause A (2015) Distributed submodular cover: Succinctly summarizing massive data. In: Proc. of the 28th NeurIPS 2015, pp. 2881–2889

• Nutov Z, Shoham E (2020) Practical budgeted submodular maximization. CoRR abs/2007.04937. arxiv:2007.04937

• Pham CV, Tran TD, Ha DTK, Thai MT (2023) Linear query approximation algorithms for non-monotone submodular maximization under knapsack constraint. In: Proceedings of the thirty-second international joint conference on artificial intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pp. 4127–4135. ijcai.org

• Pham CV, Vu QC, Ha DK, Nguyen TT (2021) Streaming algorithms for budgeted k-submodular maximization problem. In: Computational data and social networks—10th international conference, CSoNet 2021, Virtual Event, November 15-17, 2021, Proceedings, Lecture Notes in Computer Science, vol. 13116, pp. 27–38. Springer

• Sun X, Zhang J, Zhang S, Zhang Z (2024) Improved deterministic algorithms for non-monotone submodular maximization. Theor Comput Sci 984:114293

  Article  MathSciNet  Google Scholar 

• Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 32(1):41–43

  Article  MathSciNet  Google Scholar 

• Wolsey LA (1982) Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math Oper Res 7(3):410–425

  Article  MathSciNet  Google Scholar 

• Yaroslavtsev G, Zhou S, Avdiukhin D (2020) "bring your own greedy"+max: Near-optimal 1/2-approximations for submodular knapsack. In: The international conference on artificial intelligence and statistics. 108:3263–3274

Download references