{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:48:10Z","timestamp":1763466490844,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_58","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"690-701","source":"Crossref","is-referenced-by-count":18,"title":["Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"58_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-85363-3_1","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"M. Adler","year":"2008","unstructured":"Adler, M., Heeringa, B.: Approximating Optimal Binary Decision Trees. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 1\u20139. Springer, Heidelberg (2008)"},{"key":"58_CR2","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, W.R., Raghavan, P., Sudan, M.: The minimum latency problem. In: STOC, pp. 163\u2013171 (1994)","DOI":"10.1145\/195058.195125"},{"key":"58_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-642-02927-1_19","volume-title":"Automata, Languages and Programming","author":"V. Chakaravarthy","year":"2009","unstructured":"Chakaravarthy, V., Pandit, V., Roy, S., Sabharwal, Y.: Approximating Decision Trees with Multiway Branches. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 210\u2013221. Springer, Heidelberg (2009)"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Chakravarthy, V.T., Pandit, V., Roy, S., Awasthi, P., Mohania, M.: Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results. In: PODS (2007)","DOI":"10.1145\/1265530.1265538"},{"key":"58_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S.: Rounding via trees: deterministic approximation algorithms for group Steiner trees and k median. In: STOC, pp. 114\u2013123 (1998)","DOI":"10.1145\/276698.276719"},{"key":"58_CR6","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: FOCS, pp. 36\u201345 (2003)","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"58_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/11830924_10","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Chawla","year":"2006","unstructured":"Chawla, S., Roughgarden, T.: Single-source stochastic routing. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 82\u201394. Springer, Heidelberg (2006)"},{"key":"58_CR8","unstructured":"Dasgupta, S.: Analysis of a greedy active learning strategy. In: Advances in Neural Information Processing Systems, NIPS (2004)"},{"key":"58_CR9","doi-asserted-by":"crossref","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Approximating the stochastic knapsack problem: The benefit of adaptivity. In: FOCS, pp. 208\u2013217 (2004)","DOI":"10.1109\/FOCS.2004.15"},{"key":"58_CR10","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairmen problem. ACM Transactions on Algorithms\u00a03(4) (2007)","DOI":"10.1145\/1290672.1290677"},{"issue":"4","key":"58_CR11","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":"58_CR12","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. Journal of Algorithms\u00a037(1), 66\u201384 (2000)","journal-title":"Journal of Algorithms"},{"key":"58_CR13","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. Goemans","year":"2006","unstructured":"Goemans, M., 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)"},{"key":"58_CR14","unstructured":"Golovin, D., Krause, A.: Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization (2010), http:\/\/arxiv.org\/abs\/1003.3967"},{"key":"58_CR15","doi-asserted-by":"crossref","unstructured":"Guha, S., Munagala, K.: Approximation algorithms for budgeted learning problems. In: STOC, pp. 104\u2013113. ACM, New York (2007); Full version as Sequential Design of Experiments via Linear Programming, http:\/\/arxiv.org\/abs\/0805.2630v1","DOI":"10.1145\/1250790.1250807"},{"key":"58_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1007\/978-3-642-02930-1_41","volume-title":"Automata, Languages and Programming","author":"S. Guha","year":"2009","unstructured":"Guha, S., Munagala, K.: Multi-armed bandits with metric switching costs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05556, pp. 496\u2013507. Springer, Heidelberg (2009)"},{"key":"58_CR17","unstructured":"Guha, S., Munagala, K., Sarkar, S.: Information acquisition and exploitation in multichannel wireless networks. CoRR, abs\/0804.1724 (2008)"},{"key":"58_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-642-04414-4_15","volume-title":"Algorithmic Learning Theory","author":"A. Guillory","year":"2009","unstructured":"Guillory, A., Bilmes, J.: Average-Case Active Learning with Costs. In: Gavald\u00e0, R., Lugosi, G., Zeugmann, T., Zilles, S. (eds.) ALT 2009. LNCS, vol.\u00a05809, pp. 141\u2013155. Springer, Heidelberg (2009)"},{"key":"58_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hajiaghayi, M.T., R\u00e4cke, H.: Oblivious network design. In: SODA, pp. 970\u2013979 (2006)","DOI":"10.1145\/1109557.1109665"},{"key":"58_CR20","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems (full version). ArXiv (2010), http:\/\/arxiv.org\/abs\/1003.0722"},{"key":"58_CR21","doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: STOC, pp. 585\u2013594 (2003)","DOI":"10.1145\/780627.780628"},{"issue":"1","key":"58_CR22","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"L. Hyafil","year":"1976","unstructured":"Hyafil, L., Rivest, R.L.: Constructing optimal binary decision trees is NP-complete. Information Processing Lett.\u00a05(1), 15\u201317 (1976\/1977)","journal-title":"Information Processing Lett."},{"key":"58_CR23","doi-asserted-by":"crossref","unstructured":"Jaillet, P.: A priori solution of a travelling salesman problem in which a random subset of the customers are visited. Operations Research\u00a036(6) (1988)","DOI":"10.1287\/opre.36.6.929"},{"key":"58_CR24","doi-asserted-by":"crossref","unstructured":"Jia, L., Lin, G., Noubir, G., Rajaraman, R., Sundaram, R.: Universal approximations for TSP, Steiner tree, and set cover. In: STOC, pp. 386\u2013395 (2005)","DOI":"10.1145\/1060590.1060649"},{"key":"58_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/3-540-48447-7_17","volume-title":"Algorithms and Data Structures","author":"S.R. Kosaraju","year":"1999","unstructured":"Kosaraju, S.R., Przytycka, T.M., Borgstrom, R.S.: On an Optimal Split Tree Problem. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 157\u2013168. Springer, Heidelberg (1999)"},{"key":"58_CR26","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, pp. 133\u2013146 (2008)","DOI":"10.1145\/1376616.1376633"},{"key":"58_CR27","doi-asserted-by":"crossref","unstructured":"Munagala, K., Srivastava, U., Widom, J.: Optimization of continuous queries with shared expensive filters. In: PODS, pp. 215\u2013224 (2007)","DOI":"10.1145\/1265530.1265561"},{"key":"58_CR28","unstructured":"Nagarajan, V.: Approximation Algorithms for Sequencing Problems. PhD thesis, Tepper School of Business, Carnegie Mellon University (2009)"},{"key":"58_CR29","unstructured":"Nowak, R.D.: The geometry of generalized binary search. arXiv.org:0910.4397 (2009)"},{"issue":"1","key":"58_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.orl.2007.04.009","volume":"36","author":"F. Schalekamp","year":"2008","unstructured":"Schalekamp, F., Shmoys, D.: Algorithms for the universal and a priori TSP. Operations Research Letters\u00a036(1), 1\u20133 (2008)","journal-title":"Operations Research Letters"},{"key":"58_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-540-68891-4_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"D. Shmoys","year":"2008","unstructured":"Shmoys, D., Talwar, K.: A Constant Approximation Algorithm for the a priori Traveling Salesman Problem. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol.\u00a05035, pp. 331\u2013343. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:31:17Z","timestamp":1740241877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}