Adaptive Submodular Ranking and Routing

References

• Adler M, Heeringa B (2012) Approximating optimal binary decision trees. Algorithmica 62(3–4):1112–1121.Crossref, Google Scholar
• Azar Y, Gamzu I (2011) Ranking with submodular valuations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1070–1079.Crossref, Google Scholar
• Azar Y, Gamzu I, Yin X (2009) Multiple intents re-ranking. Mitzenmacher M, ed. Proc. 41st Annual ACM Sympos. Theory Comput. (ACM, New York), 669–678.Crossref, Google Scholar
• Bansal N, Gupta A, Krishnaswamy R (2010) A constant factor approximation algorithm for generalized min-sum set cover. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1539–1545.Crossref, Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Bellala G, Bhavnani S, Scott C (2011) Active diagnosis under persistent noise with unknown noise distribution: A rank-based approach. Proc. 14th Internat. Conf. Artificial Intelligence Statist., Fort Lauderdale, FL, 155–163.Google Scholar
• Bellala G, Bhavnani SK, Scott C (2012) Group-based active query selection for rapid diagnosis in time-critical situations. IEEE Trans. Inform. Theory 58(1):459–478.Crossref, Google Scholar
• Bhavnani SK, Abraham A, Demeniuk C, Gebrekristos M, Gong A, Nainwal S, Vallabha GK, Richardson RJ (2007) Network analysis of toxic chemicals and symptoms: Implications for designing first-responder systems. AMIA Annual Sympos. Proc. (American Medical Informatics Association, Bethesda, MD), 51–55.Google Scholar
• Blum A, Chalasani P, Don Coppersmith BP, Raghavan P, Sudan M (1994) The minimum latency problem. Proc. 26th Annual ACM Sympos. Theory Comput. (ACM, New York), 163–171.Google Scholar
• Calinescu G, Zelikovsky A (2005) The polymatroid steiner problems. J. Combin. Optim. 9(3):281–294.Crossref, Google Scholar
• Chakaravarthy VT, Pandit V, Roy S, Awasthi P, Mohania MK (2011) Decision trees for entity identification: Approximation algorithms and hardness results. ACM Trans. Algorithms 7(2):Article 15.Crossref, Google Scholar
• Chaudhuri K, Godfrey B, Rao S, Talwar K (2003) Paths, trees, and minimum latency tours. Proc. 44th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 36–45.Google Scholar
• Chekuri C, Pal M (2005) A recursive greedy algorithm for walks in directed graphs. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 245–253.Google Scholar
• Chen Y Javdani S, Karbasi A, Bagnell JA, Srinivasa SS, Krause A (2015) Submodular surrogates for value of information. Proc. 29th AAAI Conf. Artificial Intelligence, Austin, TX, 3511–3518.Google Scholar
• Cicalese F, Laber ES, Saettler AM (2014) Diagnosis determination: Decision trees optimizing simultaneously worst and expected testing cost. Proc. 31th Internat. Conf. Machine Learn., Beijing, China, 414–422.Google Scholar
• Dasgupta S (2004) Analysis of a greedy active learning strategy. Saul LK, Weiss Y, Bottou L, eds. Advances in Neural Information Processing Systems, vol. 17 (Curran Associates, Red Hook, NY), 337–344.Google Scholar
• Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Deshpande A, Hellerstein L, Kletenik D (2016) Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack. ACM Trans. Algorithms 12(3):Article 42.Crossref, Google Scholar
• Dinur I, Steurer D (2014) Analytical approach to parallel repetition. Sympos. Theory Comput. (ACM, New York), 624–633.Google Scholar
• Garg N, Konjevod G, Ravi R (2000) A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37(1):66–84.Crossref, Google Scholar
• 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
• Golovin D, Krause A (2017) Adaptive submodularity: A new approach to active learning and stochastic optimization. Submitted December 6, http://arxiv.org/abs/1003.3967.Google Scholar
• Golovin D, Krause A, Ray D (2010) Near-optimal Bayesian active learning with noisy observations. Advances in Neural Information Processing Systems, vol. 23 (Curran Associates, Red Hook, NY), 766–774.Google Scholar
• Grammel N, Hellerstein L, Kletenik D, Lin P (2016) Scenario submodular cover. Proc. 14th Internat. Workshop Approximation Online Algorithms, Aarhus, Denmark, 116–128.Google Scholar
• Guillory A, Bilmes J (2009) Average-case active learning with costs. Proc. 20th Internat. Conf. Algorithmic Learning Theory (Springer, Berlin, Heidelberg), 141–155.Crossref, Google Scholar
• Guillory A, Bilmes J (2011) Simultaneous learning and covering with adversarial noise. Proc. 28th Internat. Conf. Machine Learn., Bellevue, Washington, 369–376.Google Scholar
• Gupta A, Nagarajan V, Ravi R (2017) Approximation algorithms for optimal decision trees and adaptive TSP problems. Math. Oper. Res. 42(3):876–896.Link, Google Scholar
• Halperin E, Krauthgamer R (2003) Polylogarithmic inapproximability. Proc. 35th Annual Sympos. Theory Comput. (ACM, New York), 585–594.Google Scholar
• Hyafil L, Rivest RL (1976) Constructing optimal binary decision trees is NP-complete. Inform. Processing Lett. 5(1):15–17.Crossref, Google Scholar
• Ibarra OH, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4):463–468.Crossref, Google Scholar
• Im S, Sviridenko M, Van Der Zwaan R (2014) Preemptive and non-preemptive generalized min sum set cover. Math. Programming. 145(1–2):377–401.Crossref, Google Scholar
• Im S, Nagarajan V, van der Zwaan R (2016) Minimum latency submodular cover. ACM Trans. Algorithms, 13(1):1–28.Google Scholar
• Javdani SH, Chen Y, Karbasi A, Krause A, Bagnell D, Srinivasa SS (2014) Near optimal Bayesian active learning for decision making. Proc. 17th Internat. Conf. Artificial Intelligence Statistics, Reykjavik, Iceland, 430–438.Google Scholar
• Kambadur P, Nagarajan V, Navidi F (2017) Adaptive submodular ranking. Integer Programming Combin. Optim. 19th Internat. Conf. Proc., Lecture Notes in Computer Science, vol. 10328 (Springer, Cham, Switzerland), 317–329.Google Scholar
• Kempe D, Kleinberg JM, Tardos É (2015) Maximizing the spread of influence through a social network. Theory Comput. 11:105–147.Crossref, Google Scholar
• Kosaraju SR, Przytycka TM, Borgstrom RS (1999) On an optimal split tree problem. Proc. 6th Internat. Workshop Algorithms Data Structures, Vancouver, Canada, 157–168.Google Scholar
• Lim ZW, Hsu D, Lee WS (2015) Adaptive stochastic optimization: From sets to paths. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 28 (Curran Associates, Red Hook, NY), 1585–1593.Google Scholar
• Lin H, Bilmes J (2011) A class of submodular functions for document summarization. Proc. 49th Annual Meeting Assoc. Comput. Linguistics, Portland, OR, 510–520.Google Scholar
• 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
• Prasad A, Jegelka S, Batra D (2014) Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets. Advances in Neural Information Processing Systems, vol. 27 (Curran Associates, Red Hook, NY), 2645–2653.Google Scholar
• Shapley LS (1971) Cores of convex games. Internat. J. Game Theory 1(1):11–26.Crossref, Google Scholar
• Singh A, Krause A, Guestrin C, Kaiser WJ (2009) Efficient informative sensing using multiple robots. J. Artificial Intelligence Res. 34:707–755.Crossref, Google Scholar
• Skutella M, Williamson DP (2011) A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6):433–436.Crossref, Google Scholar
• Wolsey LA (1982) An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4):385–393.Crossref, Google Scholar