Minimum Cost Adaptive Submodular Cover

References

• [1] Adamczyk M, Sviridenko M, Ward J (2016) Submodular stochastic probing on matroids. Math. Oper. Res. 41(3):1022–1038.Link, Google Scholar
• [2] Adler M, Heeringa B (2012) Approximating optimal binary decision trees. Algorithmica 62(3–4):1112–1121.Crossref, Google Scholar
• [3] Agarwal A, Assadi S, Khanna S (2019) Stochastic submodular cover with limited adaptivity. SODA’19 Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 323–342.Google Scholar
• [4] Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• [5] Azar Y, Gamzu I (2011) Ranking with submodular valuations. Proc. Twenty-Second Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1070–1079.Google Scholar
• [6] Bansal N, Batra J, Farhadi M, Tetali P (2023) On min sum vertex cover and generalized min sum set cover. SIAM J. Comput. 52(2):327–357.Crossref, Google Scholar
• [7] Bradac D, Singla S, Zuzic G (2019) (Near) optimal adaptivity gaps for stochastic multi-value probing. Approximation, Randomization, and Combinatorial Optimization, vol. 145 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 49:1–49:21.Google Scholar
• [8] Butterworth R (1972) Some reliability fault-testing models. Oper. Res. 20(2):335–343.Link, Google Scholar
• [9] Chvátal V (1979) A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3):233–235.Link, Google Scholar
• [10] Cicalese F, Jacobs T, Laber ES, Molinaro M (2010) On greedy algorithms for decision trees. 21st Internat. Sympos. Algorithms Comput. ISAAC (Springer, Berlin, Heidelberg), 206–217.Crossref, Google Scholar
• [11] Dasgupta S (2004) Analysis of a greedy active learning strategy. Adv. Neural Inform. Processing Systems 17:337–344.Google Scholar
• [12] Dinur I, Steurer D (2014) Analytical approach to parallel repetition. Proc. 46th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 624–633.Google Scholar
• [13] Esfandiari H, Karbasi A, Mirrokni V (2021) Adaptivity in adaptive submodularity. Proc. 34th Conf. Learn. Theory, vol. 134 (PMLR, New York), 1823–1846.Google Scholar
• [14] Feige U, Lovász L, Tetali P (2004) Approximating min sum set cover. Algorithmica 40(4):219–234.Crossref, Google Scholar
• [15] Garey M, Graham R (1974) Performance bounds on the splitting algorithm for binary testing. Acta Inform. 3:347–355.Crossref, Google Scholar
• [16] Ghuge R, Gupta A, Nagarajan V (2024) The power of adaptivity for stochastic submodular cover. Oper. Res. 72(3):1156–1176.Link, Google Scholar
• [17] Goemans M, Vondrák J (2006) Stochastic covering and adaptivity. LATIN 2006 Theoret. Inform. (Springer, Berlin, Heidelberg), 532–543.Crossref, Google Scholar
• [18] Golovin D, Krause A (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artificial Intelligence Res. 42:427–486.Google Scholar
• [19] Golovin D, Krause A (2017) Adaptive submodularity: A new approach to active learning and stochastic optimization. Preprint, submitted December 6, https://arxiv.org/abs/1003.3967.Google Scholar
• [20] Golovin D, Gupta A, Kumar A, Tangwongsan K (2008) All-norms and all-l_p-norms approximation algorithms. IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. FSTTCS (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 199–210.Google Scholar
• [21] Grammel N, Hellerstein L, Kletenik D, Lin P (2016) Scenario submodular cover. Internat. Workshop Approximation Online Algorithms (Springer, Cham, Switzerland), 116–128. Google Scholar
• [22] Guestrin C, Krause A, Singh AP (2005) Near-optimal sensor placements in gaussian processes. Proc. 22nd Internat. Conf. Machine Learn. (Association for Computing Machinery, New York), 265–272.Google Scholar
• [23] Guillory A, Bilmes JA (2009) Average-case active learning with costs. Algorithmic Learn. Theory, Lecture Notes in Computer Science, vol. 5809 (Springer, Berlin, Heidelberg), 141–155.Crossref, Google Scholar
• [24] Gupta A, Nagarajan V, Ravi R (2017a) Approximation algorithms for optimal decision trees and adaptive TSP problems. Math. Oper. Res. 42(3):876–896.Link, Google Scholar
• [25] Gupta A, Nagarajan V, Singla S (2017b) Adaptivity gaps for stochastic probing: Submodular and XOS functions. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1688–1702.Google Scholar
• [26] Hellerstein L, Kletenik D (2018) Revisiting the approximation bound for stochastic submodular cover. J. Artificial Intelligence Res. 63:265–279.Crossref, Google Scholar
• [27] Hellerstein L, Kletenik D, Parthasarathy S (2021) A tight bound for stochastic submodular cover. J. Artificial Intelligence Res. 71:347–370.Crossref, Google Scholar
• [28] Hyafil L, Rivest RL (1976) Constructing optimal binary decision trees is NP-complete. Inform. Processing Lett. 5(1):15–17.Crossref, Google Scholar
• [29] Im S, Nagarajan V, van der Zwaan R (2016) Minimum latency submodular cover. ACM Trans. Algorithms 13(1):13.Google Scholar
• [30] Kempe D, Kleinberg JM, Tardos É (2015) Maximizing the spread of influence through a social network. Theory Comput. 11:105–147.Crossref, Google Scholar
• [31] Kosaraju SR, Przytycka TM, Borgstrom RS (1999) On an optimal split tree problem. Proc. 6th Internat. Workshop Algorithms Data Structures (Springer, Berlin, Heidelberg), 157–168.Google Scholar
• [32] Li R, Liang P, Mussmann S (2020) A tight analysis of greedy yields subexponential time approximation for uniform decision tree. Proc. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 102–121.Google Scholar
• [33] Mitten L (1960) An analytic solution to the least cost testing sequence problem. J. Indust. Engrg. 11(1):16–17.Google Scholar
• [34] Munagala K, Babu S, Motwani R, Widom J (2005) The pipelined set cover problem. 10th Internat. Conf. Database Theory ICDT (Springer, Berlin, Heidelberg), 83–98.Google Scholar
• [35] Nan F, Saligrama V (2017) Comments on the proof of adaptive stochastic set cover based on adaptive submodularity and its implications for the group identification problem in “group-based active query selection for rapid diagnosis in time-critical situations”. IEEE Trans. Inform. Theory 63(11):7612–7614.Crossref, Google Scholar
• [36] Navidi F, Kambadur P, Nagarajan V (2020) Adaptive submodular ranking and routing. Oper. Res. 68(3):856–877.Link, Google Scholar
• [37] Tong G, Wu W, Tang S, Du DZ (2017) Adaptive influence maximization in dynamic social networks. IEEE/ACM Trans. Networking 25(1):112–125.Crossref, Google Scholar
• [38] Wolsey L (1982) An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4):385–393.Crossref, Google Scholar