{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:59Z","timestamp":1763468099216,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_41","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"485-497","source":"Crossref","is-referenced-by-count":8,"title":["Minimum Latency Submodular Cover"],"prefix":"10.1007","author":[{"given":"Sungjin","family":"Im","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruben","family":"van der Zwaan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Azar, Y., Gamzu, I.: Ranking with submodular valuations. In: SODA 2011, pp. 1070\u20131079 (2011)","key":"41_CR1","DOI":"10.1137\/1.9781611973082.81"},{"doi-asserted-by":"crossref","unstructured":"Azar, Y., Gamzu, I., Yin, X.: Multiple intents re-ranking. In: STOC 2009, pp. 669\u2013678 (2009)","key":"41_CR2","DOI":"10.1145\/1536414.1536505"},{"doi-asserted-by":"crossref","unstructured":"Bansal, N., Gupta, A., Krishnaswamy, R.: A constant factor approximation algorithm for generalized min-sum set cover. In: SODA 2010, pp. 1539\u20131545 (2010)","key":"41_CR3","DOI":"10.1137\/1.9781611973075.125"},{"issue":"2","key":"41_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A. Bar-Noy","year":"1998","unstructured":"Bar-Noy, A., Bellare, M., Halld\u00f3rsson, M.M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inf. Comput.\u00a0140(2), 183\u2013202 (1998)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an n 1\/4 approximation for densest k-subgraph. In: STOC 2010, pp. 201\u2013210 (2010)","key":"41_CR5","DOI":"10.1145\/1806689.1806719"},{"issue":"3","key":"41_CR6","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s10878-005-1412-9","volume":"9","author":"G. Calinescu","year":"2005","unstructured":"Calinescu, G., Zelikovsky, A.: The polymatroid steiner problems. Journal of Combinatorial Optimization\u00a09(3), 281\u2013294 (2005)","journal-title":"Journal of Combinatorial Optimization"},{"unstructured":"Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: SODA 2000, pp. 106\u2013115 (2000)","key":"41_CR7"},{"key":"41_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-642-20807-2_8","volume-title":"Integer Programming and Combinatoral Optimization","author":"D. Chakrabarty","year":"2011","unstructured":"Chakrabarty, D., Swamy, C.: Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol.\u00a06655, pp. 92\u2013103. Springer, Heidelberg (2011)"},{"doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: FOCS 2003, pp. 36\u201345 (2003)","key":"41_CR9","DOI":"10.1109\/SFCS.2003.1238179"},{"issue":"1","key":"41_CR10","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.dam.2005.07.010","volume":"154","author":"C. Chekuri","year":"2006","unstructured":"Chekuri, C., Even, G., Kortsarz, G.: A greedy approximation algorithm for the group steiner problem. Discrete Applied Mathematics\u00a0154(1), 15\u201334 (2006)","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Chekuri, C., P\u00e1l, M.: A recursive greedy algorithm for walks in directed graphs. In: FOCS 2005, pp. 245\u2013253 (2005)","key":"41_CR11"},{"doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairmen problem. ACM Transactions on Algorithms\u00a03(4) (2007)","key":"41_CR12","DOI":"10.1145\/1290672.1290677"},{"issue":"4","key":"41_CR13","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00453-004-1110-5","volume":"40","author":"U. Feige","year":"2004","unstructured":"Feige, U., Lov\u00e1sz, L., Tetali, P.: Approximating min sum set cover. Algorithmica\u00a040(4), 219\u2013234 (2004)","journal-title":"Algorithmica"},{"issue":"1","key":"41_CR14","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N. Garg","year":"2000","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group steiner tree problem. J. Algorithms\u00a037(1), 66\u201384 (2000)","journal-title":"J. Algorithms"},{"key":"41_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1007\/11682462_50","volume-title":"LATIN 2006: Theoretical Informatics","author":"M.X. Goemans","year":"2006","unstructured":"Goemans, M.X., Vondr\u00e1k, J.: Stochastic Covering and Adaptivity. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 532\u2013543. Springer, Heidelberg (2006)"},{"unstructured":"Golovin, D., Krause, A.: Adaptive submodularity: A new approach to active learning and stochastic optimization. In: COLT 2010, pp. 333\u2013345 (2010)","key":"41_CR16"},{"unstructured":"Guillory, A., Bilmes, J.A.: Online submodular set cover, ranking, and repeated active learning. In: NIPS 2011 (2011)","key":"41_CR17"},{"key":"41_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/978-3-642-14165-2_58","volume-title":"Automata, Languages and Programming","author":"A. Gupta","year":"2010","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 690\u2013701. Springer, Heidelberg (2010)"},{"issue":"1","key":"41_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.4086\/toc.2006.v002a003","volume":"2","author":"A. Gupta","year":"2006","unstructured":"Gupta, A., Srinivasan, A.: An improved approximation ratio for the covering steiner problem. Theory of Computing\u00a02(1), 53\u201364 (2006)","journal-title":"Theory of Computing"},{"doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: STOC 2003, pp. 585\u2013594 (2003)","key":"41_CR20","DOI":"10.1145\/780542.780628"},{"doi-asserted-by":"crossref","unstructured":"Im, S., Nagarajan, V., van der Zwaan, R.: Minimum latency submodular cover. CoRR, abs\/1110.2207 (2011)","key":"41_CR21","DOI":"10.1007\/978-3-642-31594-7_41"},{"issue":"3","key":"41_CR22","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1002\/rsa.10038","volume":"20","author":"G. Konjevod","year":"2002","unstructured":"Konjevod, G., Ravi, R., Srinivasan, A.: Approximation algorithms for the covering steiner problem. Random Struct. Algorithms\u00a020(3), 465\u2013482 (2002)","journal-title":"Random Struct. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Liu, Z., Parthasarathy, S., Ranganathan, A., Yang, H.: Near-optimal algorithms for shared filter evaluation in data stream systems. In: SIGMOD 2008, pp. 133\u2013146 (2008)","key":"41_CR23","DOI":"10.1145\/1376616.1376633"},{"doi-asserted-by":"crossref","unstructured":"Munagala, K., Srivastava, U., Widom, J.: Optimization of continuous queries with shared expensive filters. In: PODS 2007, pp. 215\u2013224 (2007)","key":"41_CR24","DOI":"10.1145\/1265530.1265561"},{"unstructured":"Nagarajan, V.: Approximation Algorithms for Sequencing Problems. PhD thesis. Tepper School of Business, Carnegie Mellon University (2009)","key":"41_CR25"},{"key":"41_CR26","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency. Springer, Berlin (2003)"},{"issue":"4","key":"41_CR27","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica\u00a02(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T12:12:18Z","timestamp":1743595938000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}