{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T18:34:59Z","timestamp":1717180499697},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T00:00:00Z","timestamp":1366329600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2014,11]]},"DOI":"10.1007\/s10479-013-1372-x","type":"journal-article","created":{"date-parts":[[2013,4,18]],"date-time":"2013-04-18T16:36:13Z","timestamp":1366302973000},"page":"341-359","source":"Crossref","is-referenced-by-count":5,"title":["Evader interdiction: algorithms, complexity and collateral damage"],"prefix":"10.1007","volume":"222","author":[{"given":"Matthew P.","family":"Johnson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Gutfraind","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kiyan","family":"Ahmadizadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,4,19]]},"reference":[{"key":"1372_CR1","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/1250790.1250888","volume-title":"STOC","author":"A. Agarwal","year":"2007","unstructured":"Agarwal, A., Alon, N., & Charikar, M. (2007). Improved approximation for directed cut problems. In STOC (pp. 671\u2013680)."},{"key":"1372_CR2","unstructured":"Bar-Noy, A., Khuller, S., & Schieber, B. (1995). The complexity of finding most vital arcs and nodes (Tech. Rep.). University of Maryland, College Park, MD, USA."},{"issue":"2","key":"1372_CR3","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/1502793.1502795","volume":"56","author":"J. Chuzhoy","year":"2009","unstructured":"Chuzhoy, J., & Khanna, S. (2009). Polynomial flow-cut gaps and hardness of directed cut problems. Journal of the ACM, 56(2), 7.","journal-title":"Journal of the ACM"},{"issue":"3","key":"1372_CR4","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1287\/mnsc.21.3.362","volume":"21","author":"J. H. W. Corley","year":"1974","unstructured":"Corley, J. H. W., & Chang, H. (1974). Finding the n most vital nodes in a flow network. Management Science, 21(3), 362\u2013364.","journal-title":"Management Science"},{"issue":"4","key":"1372_CR5","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0167-6377(82)90020-7","volume":"1","author":"H. W. Corley","year":"1982","unstructured":"Corley, H. W., & Sha, D. Y. (1982). Most vital links and nodes in weighted networks. Operations Research Letters, 1(4), 157\u2013160.","journal-title":"Operations Research Letters"},{"issue":"3","key":"1372_CR6","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/1367064.1367074","volume":"4","author":"G. Even","year":"2008","unstructured":"Even, G., Levi, R., Rawitz, D., Schieber, B., Shahar, S., & Sviridenko, M. (2008). Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs. ACM Transactions on Algorithms, 4(3), 34.","journal-title":"ACM Transactions on Algorithms"},{"key":"1372_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139015165","volume-title":"Graph algorithms","author":"S. Even","year":"2011","unstructured":"Even, S., & Even, G. (2011). Graph algorithms. Cambridge: Cambridge University Press."},{"issue":"4","key":"1372_CR8","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U. (1998). A threshold of ln for approximating set cover. Journal of the ACM, 45(4), 634\u2013652.","journal-title":"Journal of the ACM"},{"key":"1372_CR9","first-page":"47","volume-title":"STOC\u00a0\u201974","author":"M. R. Garey","year":"1974","unstructured":"Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1974). Some simplified NP-complete problems. In STOC\u00a0\u201974 (pp. 47\u201363). New York: ACM."},{"issue":"1","key":"1372_CR10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V., & Yannakakis, M. (1997). Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1), 3\u201320.","journal-title":"Algorithmica"},{"issue":"1","key":"1372_CR11","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/jagm.2002.1221","volume":"43","author":"D. Gaur","year":"2002","unstructured":"Gaur, D., Ibaraki, T., & Krishnamurti, R. (2002). Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem. Journal of Algorithms, 43(1), 138\u2013152.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"1372_CR12","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F. (1972). Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2), 180\u2013187.","journal-title":"SIAM Journal on Computing"},{"key":"1372_CR13","first-page":"395","volume":"1","author":"K. Glazer","year":"2006","unstructured":"Glazer, K., & Rubinstein, A. (2006). A study in the pragmatics of persuasion: a game theoretical approach. Theoretical Economics, 1, 395\u2013410.","journal-title":"Theoretical Economics"},{"key":"1372_CR14","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1145\/1109557.1109625","volume-title":"Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithm","author":"D. Golovin","year":"2006","unstructured":"Golovin, D., Nagarajan, V., & Singh, M. (2006). Approximating the k-multicut problem. In Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithm (pp. 621\u2013630). New York: ACM."},{"key":"1372_CR15","first-page":"3","volume-title":"Proceedings of the 12th INFORMS computing society conference on OR, computing, and homeland defense, INFORMS","author":"A. Gutfraind","year":"2011","unstructured":"Gutfraind, A., Hagberg, A., Izraelevitz, D., & Pan, F. (2011). Interdiction of a Markovian evader. In R. K. Wood & R. F. Dell (Eds.), Proceedings of the 12th INFORMS computing society conference on OR, computing, and homeland defense, INFORMS (pp. 3\u201315)."},{"key":"1372_CR16","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/978-3-642-01929-6_9","volume-title":"Proc. CPAIOR","author":"A. Gutfraind","year":"2009","unstructured":"Gutfraind, A., Hagberg, A., & Pan, F. (2009). Optimal interdiction of unreactive Markovian evaders. In J.\u00a0Hooker & W.-J. van Hoeve (Eds.), Lecture notes in computer science: Vol.\u00a05547. Proc. CPAIOR (pp. 102\u2013116). Berlin: Springer."},{"key":"1372_CR17","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.tcs.2012.05.021","volume":"452","author":"M. Hajiaghayi","year":"2012","unstructured":"Hajiaghayi, M., Khandekar, R., Kortsarz, G., & Mestre, J. (2012). The checkpoint problem. Theoretical Computer Science, 452, 88\u201399.","journal-title":"Theoretical Computer Science"},{"key":"1372_CR18","first-page":"671","volume-title":"FOCS","author":"S. Iwata","year":"2009","unstructured":"Iwata, S., & Nagano, K. (2009). Submodular function minimization under covering constraints. In FOCS (pp. 671\u2013680)."},{"issue":"1","key":"1372_CR19","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"D. B. Johnson","year":"1975","unstructured":"Johnson, D. B. (1975). Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 4(1), 77\u201384.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"1372_CR20","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/s00453-002-1006-1","volume":"36","author":"M. Katz","year":"2003","unstructured":"Katz, M., Nielsen, F., & Segal, M. (2003). Maintenance of a piercing set for intervals with applications. Algorithmica, 36(1), 59\u201373.","journal-title":"Algorithmica"},{"issue":"3","key":"1372_CR21","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., & Regev, O. (2008). Vertex cover might be hard to approximate to within 2\u2212\u03f5. Journal of Computer and System Sciences, 74(3), 335\u2013349.","journal-title":"Journal of Computer and System Sciences"},{"key":"1372_CR22","first-page":"634","volume-title":"ICALP (1)","author":"C. Koufogiannakis","year":"2009","unstructured":"Koufogiannakis, C., & Young, N. E. (2009). Greedy \u0394-approximation algorithm for covering with arbitrary constraints and submodular cost. In ICALP (1) (pp. 634\u2013652)."},{"issue":"1","key":"1372_CR23","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/j.tcs.2006.09.018","volume":"369","author":"A. Levin","year":"2006","unstructured":"Levin, A., & Segev, D. (2006). Partial multicuts in trees. Theoretical Computer Science, 369(1), 384\u2013395.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"1372_CR24","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/nav.3800170302","volume":"17","author":"A. W. McMasters","year":"1970","unstructured":"McMasters, A. W., & Mustin, T. M. (1970). Optimal interdiction of a supply network. Naval Research Logistics Quarterly, 17(3), 261\u2013268.","journal-title":"Naval Research Logistics Quarterly"},{"issue":"2","key":"1372_CR25","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1137\/0604028","volume":"4","author":"N. Megiddo","year":"1983","unstructured":"Megiddo, N., Zemel, E., & Hakimi, S. L. (1983). The maximum coverage location problem. SIAM Journal on Algebraic and Discrete Methods, 4(2), 253\u2013261.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"4","key":"1372_CR26","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.ipl.2008.05.007","volume":"108","author":"P. Miettinen","year":"2008","unstructured":"Miettinen, P. (2008). On the positive-negative partial set cover problem. Information Processing Letters, 108(4), 219\u2013221.","journal-title":"Information Processing Letters"},{"issue":"1","key":"1372_CR27","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0304-3975(98)00336-3","volume":"246","author":"F. Nielsen","year":"2000","unstructured":"Nielsen, F. (2000). Fast stabbing of boxes in high dimensions. Theoretical Computer Science, 246(1), 53\u201372.","journal-title":"Theoretical Computer Science"},{"key":"1372_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/0-306-48109-X_1","volume-title":"Network interdiction and stochastic integer programming","author":"F. Pan","year":"2003","unstructured":"Pan, F., Charlton, W. S., & Morton, D. P. (2003). Interdicting smuggled nuclear material. In D. Woodruff (Ed.) Network interdiction and stochastic integer programming (pp. 1\u201319). Boston: Kluwer Academic."},{"issue":"5","key":"1372_CR29","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1287\/mnsc.21.5.531","volume":"21","author":"H. D. Ratliff","year":"1975","unstructured":"Ratliff, H. D., Sicilia, G. T., & Lubore, S. H. (1975). Finding the n most vital links in flow networks. Management Science, 21(5), 531\u2013539.","journal-title":"Management Science"},{"key":"1372_CR30","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1145\/237814.238005","volume-title":"STOC \u201996","author":"N. Robertson","year":"1996","unstructured":"Robertson, N., Sanders, D. P., Seymour, P., & Thomas, R. (1996). Efficiently four-coloring planar graphs. In STOC \u201996 (pp. 571\u2013575). New York: ACM."},{"issue":"1","key":"1372_CR31","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1), 103\u2013128.","journal-title":"Theory of Computing"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-013-1372-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-013-1372-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-013-1372-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T05:03:05Z","timestamp":1688187785000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-013-1372-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,19]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,11]]}},"alternative-id":["1372"],"URL":"https:\/\/doi.org\/10.1007\/s10479-013-1372-x","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,19]]}}}