{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T16:50:27Z","timestamp":1773247827444,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,5,11]],"date-time":"2010-05-11T00:00:00Z","timestamp":1273536000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2010,7]]},"DOI":"10.1007\/s10107-010-0357-7","type":"journal-article","created":{"date-parts":[[2010,5,10]],"date-time":"2010-05-10T10:52:11Z","timestamp":1273488731000},"page":"93-118","source":"Crossref","is-referenced-by-count":29,"title":["New techniques for cost sharing in combinatorial optimization games"],"prefix":"10.1007","volume":"124","author":[{"given":"Alberto","family":"Caprara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam N.","family":"Letchford","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,5,11]]},"reference":[{"key":"357_CR1","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1287\/moor.22.1.110","volume":"22","author":"P. Bauer","year":"1997","unstructured":"Bauer P.: The circuit polytope: facets. Math. Oper. Res. 22, 110\u2013145 (1997)","journal-title":"Math. Oper. Res."},{"key":"357_CR2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s00224-007-9072-z","volume":"43","author":"M. Bl\u00e4ser","year":"2008","unstructured":"Bl\u00e4ser M., Shankar Ram L.: Approximately fair cost allocation in metric traveling salesman games. Theory Comput. Syst. 43, 19\u201337 (2008)","journal-title":"Theory Comput. Syst."},{"key":"357_CR3","first-page":"119","volume":"10","author":"O.N. Bondareva","year":"1963","unstructured":"Bondareva O.N.: Some applications of linear programming to cooperative games. Problemy Kibernetiki. 10, 119\u2013139 (1963)","journal-title":"Problemy Kibernetiki."},{"key":"357_CR4","volume-title":"The Vehicle Routing Problem","author":"J. Bramel","year":"2002","unstructured":"Bramel J., Simchi-Levi D.: Set-covering-based algorithms for the capacitated VRP. In: Toth, P., Vigo, D. (eds) The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications SIAM, Philadelphia (2002)"},{"key":"357_CR5","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1287\/opre.8.1.101","volume":"8","author":"G.B. Dantzig","year":"1960","unstructured":"Dantzig G.B., Wolfe P.: Decomposition principle for linear programs. Oper. Res. 8, 101\u2013111 (1960)","journal-title":"Oper. Res."},{"key":"357_CR6","first-page":"56","volume-title":"Annals of Mathematical Programming in Rio","author":"M.P. Araga\u00f5 de","year":"2003","unstructured":"de Araga\u00f5 M.P., Uchoa E.: Integer program reformulation for robust branch-and-cut-and-price. In: Wosley, L. (eds) Annals of Mathematical Programming in Rio, pp. 56\u201361. B\u00fazios, Brazil (2003)"},{"key":"357_CR7","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1287\/moor.24.3.751","volume":"24","author":"X. Deng","year":"1999","unstructured":"Deng X., Ibaraki T., Nagamochi H.: Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24, 751\u2013766 (1999)","journal-title":"Math. Oper. Res."},{"key":"357_CR8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"Edmonds J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. 69, 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"357_CR9","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01545526","volume":"20","author":"U. Faigle","year":"1998","unstructured":"Faigle U., Fekete S.P., Hochst\u00e4ttler W., Kern W.: On approximately fair cost allocation for the Euclidean traveling salesman problem. OR Spektrum 20, 29\u201337 (1998)","journal-title":"OR Spektrum"},{"key":"357_CR10","unstructured":"Fekete, S.P., Pulleyblank, W.R.: A note on the traveling preacher problem. Report No. 98.331, Angewandte Mathematik und Informatik, Universit\u00e4t zu K\u00f6ln (1998)"},{"key":"357_CR11","doi-asserted-by":"crossref","unstructured":"Fukasawa, R., Lysgaard, J., de Arag\u00e3o, M.P., Reis, M., Uchoa, E., Werneck, R.F.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. In Nemhauser, G., Bienstock, D. (eds.) Integer Programming and Combinatorial Optimization 10, pp. 1\u201315. Lecture Notes in Computer Science 3064, Berlin, Springer (2004)","DOI":"10.1007\/978-3-540-25960-2_1"},{"key":"357_CR12","first-page":"47","volume-title":"Contributions to the Theory of Games, vol. 4","author":"D.B. Gillies","year":"1959","unstructured":"Gillies D.B.: Solutions to general non-zero-sum games. In: Tucker, A.W., Luce, R.D. (eds) Contributions to the Theory of Games, vol. 4, pp. 47\u201385. Princeton University Press, Princeton (1959)"},{"key":"357_CR13","unstructured":"Goemans, M.X.: Private communication (2004)"},{"key":"357_CR14","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/S0196-6774(03)00098-1","volume":"50","author":"M.X. Goemans","year":"2004","unstructured":"Goemans M.X., Skutella M.: Cooperative facility location games. J. Algorithms 50, 194\u2013214 (2004)","journal-title":"J. Algorithms"},{"key":"357_CR15","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02592333","volume":"72","author":"M. G\u00f6the-Lundgren","year":"1996","unstructured":"G\u00f6the-Lundgren M., J\u00f6rnsten K., V\u00e4rbrand P.: On the nucleolus of the basic vehicle routing game. Math. Program. 72, 83\u2013100 (1996)","journal-title":"Math. Program."},{"key":"357_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01584227","volume":"21","author":"D. Granot","year":"1981","unstructured":"Granot D., Huberman G.: Minimum cost spanning tree games. Math. Program. 21, 1\u201318 (1981)","journal-title":"Math. Program."},{"key":"357_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel M., Lov\u00e1sz L., Schrijver A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"key":"357_CR18","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"Gr\u00f6tschel M., Padberg M.W.: On the symmetric travelling salesman problem I: inequalities. Math. Program. 16, 265\u2013280 (1979)","journal-title":"Math. Program."},{"key":"357_CR19","volume-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel M., Padberg M.W. et\u00a0al.: Polyhedral theory. In: Lawler, E.L. (eds) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester (1985)"},{"key":"357_CR20","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1287\/moor.11.4.537","volume":"11","author":"M. Gr\u00f6tschel","year":"1986","unstructured":"Gr\u00f6tschel M., Pulleyblank W.: Clique tree inequalities and the symmetric travelling salesman problem. Math. Oper. Res. 11, 537\u2013569 (1986)","journal-title":"Math. Oper. Res."},{"key":"357_CR21","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1016\/0377-2217(94)00025-8","volume":"85","author":"L. Gouveia","year":"1995","unstructured":"Gouveia L.: A result on projection for the vehicle routing problem. Eur. J. Opl. Res. 85, 610\u2013684 (1995)","journal-title":"Eur. J. Opl. Res."},{"key":"357_CR22","first-page":"93","volume":"17","author":"D.J. Houck","year":"1980","unstructured":"Houck D.J., Picard J.-C., Queyranne M., Vemuganti R.R.: The travelling salesman problem as a constrained shortest path problem: theory and computational experience. Opsearch 17, 93\u2013109 (1980)","journal-title":"Opsearch"},{"key":"357_CR23","volume-title":"Algorithmic Game Theory","author":"K. Jain","year":"2007","unstructured":"Jain K., Mahdian M.: Cost sharing. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds) Algorithmic Game Theory, Cambridge University Press, Cambridge (2007)"},{"key":"357_CR24","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s10107-002-0336-8","volume":"94","author":"A.N. Letchford","year":"2002","unstructured":"Letchford A.N., Eglese R.W., Lysgaard J.: Multistars, partial multistars and the capacitated vehicle routing problem. Math. Program. 94, 21\u201340 (2002)","journal-title":"Math. Program."},{"key":"357_CR25","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10107-005-0652-x","volume":"105","author":"A.N. Letchford","year":"2006","unstructured":"Letchford A.N., Salazar Gonzalez J.J.: Projection results for vehicle routing. Math. Program. 105, 251\u2013274 (2006)","journal-title":"Math. Program."},{"key":"357_CR26","volume-title":"The Traveling Salesman Problem and Its Variations","author":"D. Naddef","year":"2001","unstructured":"Naddef D.: Polyhedral theory and branch-and-cut algorithms for the symmetric TSP. In: Gutin, G., Punnen, A. (eds) The Traveling Salesman Problem and Its Variations, Kluwer, Dordrecht (2001)"},{"key":"357_CR27","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01586945","volume":"51","author":"D. Naddef","year":"1991","unstructured":"Naddef D., Rinaldi G.: The symmetric traveling salesman polytope and its graphical relaxation: composition of valid inequalities. Math. Program. 51, 359\u2013400 (1991)","journal-title":"Math. Program."},{"key":"357_CR28","volume-title":"Theory of Games and Economic Behaviour","author":"J. von Neumann","year":"1947","unstructured":"von Neumann J., Morgenstern O.: Theory of Games and Economic Behaviour. Princeton University Press, Princeton (1947)"},{"key":"357_CR29","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/j.dam.2003.08.005","volume":"138","author":"Y. Okamoto","year":"2004","unstructured":"Okamoto Y.: Traveling salesman games with the Monge property. Discr. Appl. Math. 138, 349\u2013369 (2004)","journal-title":"Discr. Appl. Math."},{"key":"357_CR30","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"M.W. Padberg","year":"1982","unstructured":"Padberg M.W., Rao M.R.: Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7, 67\u201380 (1982)","journal-title":"Math. Oper. Res."},{"key":"357_CR31","doi-asserted-by":"crossref","unstructured":"Pal, M., Tardos, E.: Group strategy proof mechanisms via primal-dual algorithms. In: Proceedings of the 44th annual IEEE symposium on foundations of computer science (FOCS 2003), pp. 584\u2013593 (2003)","DOI":"10.1109\/SFCS.2003.1238231"},{"key":"357_CR32","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0308-8","volume-title":"Introduction to the Theory of Cooperative Games","author":"B. Peleg","year":"2003","unstructured":"Peleg B., Sudholter P.: Introduction to the Theory of Cooperative Games. Kluwer, Dordrecht (2003)"},{"key":"357_CR33","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF01585702","volume":"53","author":"J.A.M. Potters","year":"1992","unstructured":"Potters J.A.M., Curiel I.J., Tijs S.H.: Traveling salesman games. Math. Program. 53, 199\u2013211 (1992)","journal-title":"Math. Program."},{"key":"357_CR34","first-page":"341","volume-title":"Graph Theory and Related Topics","author":"P.D. Seymour","year":"1979","unstructured":"Seymour P.D.: Sums of circuits. In: Bondy, J.A., Murty, U.S.R. (eds) Graph Theory and Related Topics, pp. 341\u2013355. Academic Press, London (1979)"},{"key":"357_CR35","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1002\/nav.3800140404","volume":"14","author":"L.S. Shapley","year":"1967","unstructured":"Shapley L.S.: On balanced sets and cores. Nav. Res. Log. Quart. 14, 453\u2013460 (1967)","journal-title":"Nav. Res. Log. Quart."},{"key":"357_CR36","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01753437","volume":"1","author":"L.S. Shapley","year":"1972","unstructured":"Shapley L.S., Shubik M.: The assignment game I: the core. Int. J. Game Theory 1, 111\u2013130 (1972)","journal-title":"Int. J. Game Theory"},{"key":"357_CR37","doi-asserted-by":"crossref","unstructured":"Shubik, M.: Game theory models and methods in political economy. In Arrow, K.J., Intriligator, M.D. (eds.) Handbook of Mathematical Economics, vol. I. North-Holland, pp. 285\u2013330 (1981)","DOI":"10.1016\/S1573-4382(81)01011-4"},{"key":"357_CR38","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0167-6377(89)90030-8","volume":"8","author":"A. Tamir","year":"1988","unstructured":"Tamir A.: On the core of a traveling salesman cost allocation game. Oper. Res. Lett. 8, 31\u201334 (1988)","journal-title":"Oper. Res. Lett."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0357-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-010-0357-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-010-0357-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T05:50:08Z","timestamp":1559109008000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-010-0357-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5,11]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["357"],"URL":"https:\/\/doi.org\/10.1007\/s10107-010-0357-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,5,11]]}}}