{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:38:02Z","timestamp":1742913482096,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319623887"},{"type":"electronic","value":"9783319623894"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62389-4_14","type":"book-chapter","created":{"date-parts":[[2017,6,30]],"date-time":"2017-06-30T15:07:46Z","timestamp":1498835266000},"page":"162-174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Reoptimization of Minimum Latency Problem"],"prefix":"10.1007","author":[{"given":"Wenkai","family":"Dai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,1]]},"reference":[{"issue":"3","key":"14_CR1","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1002\/net.10091","volume":"42","author":"C Archetti","year":"2003","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the traveling salesman problem. Networks 42(3), 154\u2013159 (2003)","journal-title":"Networks"},{"issue":"17","key":"14_CR2","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1016\/j.dam.2010.08.003","volume":"158","author":"C Archetti","year":"2010","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the 0\u20131 knapsack problem. Discret. Appl. Math. 158(17), 1879\u20131887 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"14_CR3","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1016\/j.jda.2008.12.001","volume":"7","author":"G Ausiello","year":"2009","unstructured":"Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.: Reoptimization of minimum and maximum traveling salesman\u2019s tours. J. Discret. Algorithms 7(4), 453\u2013463 (2009). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1570866708001019","journal-title":"J. Discret. Algorithms"},{"issue":"2","key":"14_CR4","first-page":"83","volume":"2","author":"HJ B\u00f6ckenhauer","year":"2007","unstructured":"B\u00f6ckenhauer, H.J., Forlizzi, L., Hromkovic, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: On the approximability of TSP on local modifications of optimally solved instances. Algorithmic Oper. Res. 2(2), 83 (2007). https:\/\/journals.lib.unb.ca\/index.php\/AOR\/article\/view\/2803","journal-title":"Algorithmic Oper. Res."},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-642-00982-2_12","volume-title":"Language and Automata Theory and Applications","author":"T Berg","year":"2009","unstructured":"Berg, T., Hempel, H.: Reoptimization of traveling salesperson problems: changing single edge-weights. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 141\u2013151. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-00982-2_12"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-69903-3_24","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"D Bil\u00f2","year":"2008","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Widmayer, P., Zych, A.: Reoptimization of steiner trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol. 5124, pp. 258\u2013269. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-69903-3_24"},{"issue":"2","key":"14_CR7","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s00453-010-9419-8","volume":"61","author":"D Bil\u00f2","year":"2011","unstructured":"Bil\u00f2, D., B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lovi\u010d, R., M\u00f6mke, T., Seibert, S., Zych, A.: Reoptimization of the shortest common superstring problem. Algorithmica 61(2), 227\u2013251 (2011). http:\/\/dx.doi.org\/10.1007\/s00453-010-9419-8","journal-title":"Algorithmica"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-540-93980-1_16","volume-title":"Approximation and Online Algorithms","author":"D Bil\u00f2","year":"2009","unstructured":"Bil\u00f2, D., Widmayer, P., Zych, A.: Reoptimization of weighted graph and covering problems. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426, pp. 201\u2013213. Springer, Heidelberg (2009). doi:10.1007\/978-3-540-93980-1_16"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-642-32589-2_19","volume-title":"Mathematical Foundations of Computer Science 2012","author":"D Bil\u00f2","year":"2012","unstructured":"Bil\u00f2, D., Zych, A.: New advances in reoptimizing the minimum steiner tree problem. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 184\u2013197. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-32589-2_19"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC 1994, NY, USA, pp. 163\u2013171 (1994). http:\/\/doi.acm.org\/10.1145\/195058.195125","DOI":"10.1145\/195058.195125"},{"key":"14_CR11","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2014.04.004","volume":"540","author":"N Boria","year":"2014","unstructured":"Boria, N., Croce, F.D.: Reoptimization in machine scheduling. Theor. Comput. Sci. 540, 13\u201326 (2014). http:\/\/dx.doi.org\/10.1016\/j.tcs.2014.04.004","journal-title":"Theor. Comput. Sci."},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2012.10.037","volume":"514","author":"N Boria","year":"2013","unstructured":"Boria, N., Monnot, J., Paschos, V.T.: Reoptimization of maximum weight induced hereditary subgraph problems. Theor. Comput. Sci. 514, 61\u201374 (2013). http:\/\/dx.doi.org\/10.1016\/j.tcs.2012.10.037","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"14_CR13","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1051\/ro\/2011114","volume":"45","author":"N Boria","year":"2011","unstructured":"Boria, N., Paschos, V.T.: A survey on combinatorial optimization in dynamic environments. RAIRO - Oper. Res. 45(3), 241\u2013294 (2011). http:\/\/dx.doi.org\/10.1051\/ro\/2011114","journal-title":"RAIRO - Oper. Res."},{"key":"14_CR14","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, Proceedings, pp. 36\u201345, October 2003"},{"key":"14_CR15","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1142\/9781848162778_0004","volume-title":"Computability in Context: Computation and Logic in the Real World","author":"VB Giorgio Ausiello","year":"2011","unstructured":"Giorgio Ausiello, V.B., Escoffier, B.: Complexity and approximation in reoptimization. In: Cooper, S.B., Sorbi, A. (eds.) Computability in Context: Computation and Logic in the Real World, pp. 101\u2013129. World Scientific, Singapore (2011)"},{"key":"14_CR17","unstructured":"Goyal, K., M\u00f6mke, T.: Robust reoptimization of Steiner trees. In: 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 16\u201318, 2015, Bangalore, India, pp. 10\u201324 (2015). http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2015.10"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-540-77566-9_5","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H-J B\u00f6ckenhauer","year":"2008","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 50\u201365. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-77566-9_5"},{"key":"14_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04616-6","volume-title":"Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics","author":"J Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J.: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer-Verlag New York Inc., New York (2001)"},{"issue":"3","key":"14_CR20","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.ipl.2014.11.003","volume":"115","author":"J Monnot","year":"2015","unstructured":"Monnot, J.: A note on the traveling salesman reoptimization problem under vertex insertion. Inf. Process. Lett. 115(3), 435\u2013438 (2015). http:\/\/dx.doi.org\/10.1016\/j.ipl.2014.11.003","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"14_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"CH Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The traveling salesman problem with distances one and two. Math. Oper. Res. 18(1), 1\u201311 (1993). http:\/\/dx.doi.org\/10.1287\/moor.18.1.1","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"14_CR22","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(96)00042-X","volume":"72","author":"MW Sch\u00e4ffter","year":"1997","unstructured":"Sch\u00e4ffter, M.W.: Scheduling with forbidden sets. Discrete Appl. Math. 72(1\u20132), 155\u2013166 (1997). http:\/\/dx.doi.org\/10.1016\/S0166-218X(96)00042-X","journal-title":"Discrete Appl. Math."},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Sitters, R.: The minimum latency problem is NP-hard for weighted trees. In: Proceedings of the 9th Integer Programming and Combinatorial Optimization Conference, pp. 230\u2013239 (2002)","DOI":"10.1007\/3-540-47867-1_17"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62389-4_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:23:54Z","timestamp":1709810634000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-62389-4_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319623887","9783319623894"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62389-4_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"1 July 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 August 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon2017.comp.polyu.edu.hk\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}