{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:43:09Z","timestamp":1725496989251},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771043"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77105-0_54","type":"book-chapter","created":{"date-parts":[[2007,12,3]],"date-time":"2007-12-03T06:59:37Z","timestamp":1196665177000},"page":"503-514","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Mechanisms for the Graphical TSP and Other Graph Traversal Problems"],"prefix":"10.1007","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Luca","family":"Forlizzi","sequence":"additional","affiliation":[]},{"given":"Luciano","family":"Gual\u00e0","sequence":"additional","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"54_CR1","first-page":"482","volume-title":"Proc. of the 42nd Annual IEEE Symp. on Foundations of Computer Science (FOCS)","author":"A. Archer","year":"2001","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: Archer, A. (ed.) Proc. of the 42nd Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 482\u2013491. IEEE Computer Society Press, Los Alamitos (2001)"},{"issue":"1","key":"54_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(01)00287-0","volume":"285","author":"H.-J. B\u00f6ckenhauer","year":"2002","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Klasing, R., Seibert, S., Unger, W.: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoretical Computer Science\u00a0285(1), 3\u201324 (2002)","journal-title":"Theoretical Computer Science"},{"key":"54_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/trsc.35.4.345.10433","volume":"35","author":"L. Brotcorne","year":"2001","unstructured":"Brotcorne, L., Labb\u00e9, M., Marcotte, P., Savard, G.: A bilevel model for toll optimization on a multicommodity transportation network. Transportation Science\u00a035, 1\u201314 (2001)","journal-title":"Transportation Science"},{"key":"54_CR4","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, GSIA, Carnegy Mellon University (1976)"},{"key":"54_CR5","first-page":"73","volume":"13","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: The Chinese postman problem. Operations Research\u00a013, 73\u201377 (1965)","journal-title":"Operations Research"},{"key":"54_CR6","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J. Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.L.: Matching, Euler tours and the chinese postman. Math. Programming\u00a05, 88\u2013124 (1973)","journal-title":"Math. Programming"},{"issue":"3","key":"54_CR7","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/322139.322150","volume":"26","author":"G.N. Frederickson","year":"1979","unstructured":"Frederickson, G.N.: Approximation algorithms for some postman problems. J. ACM\u00a026(3), 538\u2013554 (1979)","journal-title":"J. ACM"},{"key":"54_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1007\/11549468_103","volume-title":"Euro-Par 2005 Parallel Processing","author":"L. Gual\u00e0","year":"2005","unstructured":"Gual\u00e0, L., Proietti, G.: Efficient truthful mechanisms for the single-source shortest paths tree problem. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol.\u00a03648, pp. 941\u2013951. Springer, Heidelberg (2005)"},{"key":"54_CR9","first-page":"252","volume-title":"Proc. of the 42nd Annual IEEE Symp. on Foundations of Computer Science (FOCS)","author":"J. Hershberger","year":"2001","unstructured":"Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth? In: Proc. of the 42nd Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 252\u2013259. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"54_CR10","volume-title":"Proc. of the 6th ACM Conf. on Electronic Commerce (EC)","author":"M.-Y. Kao","year":"2005","unstructured":"Kao, M.-Y., Li, X.-Y., Wang, W.: Towards truthful mechanisms for binary demand games: A general framework. In: Proc. of the 6th ACM Conf. on Electronic Commerce (EC), ACM Press, New York (2005)"},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1002\/net.3230060305","volume":"6","author":"J.K. Lenstra","year":"1976","unstructured":"Lenstra, J.K., Kan, A.G.H.R.: On general routing problems. Networks\u00a06, 273\u2013280 (1976)","journal-title":"Networks"},{"key":"54_CR12","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/game.1999.0790","volume":"35","author":"N. Nisan","year":"2001","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic Behaviour\u00a035, 166\u2013196 (2001)","journal-title":"Games and Economic Behaviour"},{"issue":"3","key":"54_CR13","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1145\/321958.321974","volume":"23","author":"C. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.: On the complexity of edge traversing. J. ACM\u00a023(3), 544\u2013554 (1976)","journal-title":"J. ACM"},{"key":"54_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/11944874_34","volume-title":"Internet and Network Economics","author":"P. Penna","year":"2006","unstructured":"Penna, P., Proietti, G., Widmayer, P.: Strongly polynomial-time truthful mechanisms in one shot. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol.\u00a04286, pp. 377\u2013388. Springer, Heidelberg (2006)"},{"key":"54_CR15","unstructured":"Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 267\u2013276 (2002)"},{"key":"54_CR16","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1145\/1073970.1073999","volume-title":"Proc. of the 17th ACM Symp. on Parallel Algorithms and Architectures (SPAA)","author":"G. Proietti","year":"2005","unstructured":"Proietti, G., Widmayer, P.: A truthful mechanism for the non-utilitarian minimum radius spanning tree problem. In: Proc. of the 17th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 195\u2013202. ACM Press, New York (2005)"},{"issue":"4","key":"54_CR17","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1137\/S0895480197331454","volume":"12","author":"B. Raghavachari","year":"1999","unstructured":"Raghavachari, B., Veerasamy, J.: A 3\/2-approximation algorithm for the mixed postman problem. SIAM J. Discrete Math.\u00a012(4), 425\u2013433 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"54_CR18","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Internet and Network Economics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77105-0_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:00:35Z","timestamp":1619521235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77105-0_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771043"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77105-0_54","relation":{},"subject":[]}}