2026-08-14T17:12:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17029 2024-03-06T10:59:00Z ddc:004 open_access

Correlated Stochastic Knapsack with a Submodular Objective Yang, Sheng Khuller, Samir Choudhary, Sunav Mitra, Subrata Mahadik, Kanak Stochastic Knapsack Submodular Optimization Stochastic Optimization We study the correlated stochastic knapsack problem of a submodular target function, with optional additional constraints. We utilize the multilinear extension of submodular function, and bundle it with an adaptation of the relaxed linear constraints from Ma [Mathematics of Operations Research, Volume 43(3), 2018] on correlated stochastic knapsack problem. The relaxation is then solved by the stochastic continuous greedy algorithm, and rounded by a novel method to fit the contention resolution scheme (Feldman et al. [FOCS 2011]). We obtain a pseudo-polynomial time (1 - 1/√e)/2 ≃ 0.1967 approximation algorithm with or without those additional constraints, eliminating the need of a key assumption and improving on the (1 - 1/∜e)/2 ≃ 0.1106 approximation by Fukunaga et al. [AAAI 2019]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sheng Yang and Samir Khuller and Sunav Choudhary and Subrata Mitra and Kanak Mahadik 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.91 urn:nbn:de:0030-drops-170296 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.91 eng https://creativecommons.org/licenses/by/4.0/legalcode