{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T05:05:38Z","timestamp":1761973538473,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382321"},{"type":"electronic","value":"9783642382338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38233-8_22","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T12:57:16Z","timestamp":1368622636000},"page":"264-275","source":"Crossref","is-referenced-by-count":2,"title":["Shortest Paths with Bundles and Non-additive Weights Is Hard"],"prefix":"10.1007","author":[{"given":"Paul W.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antony","family":"McCabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","unstructured":"Archer, A., Papadimitriou, C., Talwar, K., Tardos, E.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: Procs. of 14th SODA, pp. 205\u2013214 (2003)"},{"key":"22_CR2","unstructured":"Archer, A., Tardos, E.: Frugal path mechanisms. In: Procs. of 13th SODA, pp. 991\u2013999 (2002)"},{"issue":"6","key":"22_CR3","doi-asserted-by":"publisher","first-page":"1587","DOI":"10.1137\/090772988","volume":"40","author":"P. Briest","year":"2011","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation techniques for utilitarian mechanism design. SIAM J. Comput.\u00a040(6), 1587\u20131622 (2011)","journal-title":"SIAM J. Comput."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Chen, N., Elkind, E., Gravin, N., Petrov, F.: Frugal mechanism design via spectral techniques. In: Procs. of 51st FOCS, pp. 755\u2013764 (2010)","DOI":"10.1109\/FOCS.2010.77"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Clarke, E.H.: Multipart pricing of public goods. Public Choice\u00a011(1) (1971)","DOI":"10.1007\/BF01726210"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"issue":"1","key":"22_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.tcs.2009.09.032","volume":"411","author":"Y. Du","year":"2010","unstructured":"Du, Y., Sami, R., Shi, Y.: Path auctions with multiple edge ownership. Theoretical Computer Science\u00a0411(1), 293\u2013300 (2010)","journal-title":"Theoretical Computer Science"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Elkind, E., Goldberg, L.A., Goldberg, P.W.: Frugality ratios and improved truthful mechanisms for vertex cover. In: Procs. of the 8th ACM-EC, pp. 336\u2013345 (2007)","DOI":"10.1145\/1250910.1250959"},{"key":"22_CR9","unstructured":"Elkind, E., Sahai, A., Steiglitz, K.: Frugality in path auctions. In: Procs. of 15th SODA, pp. 701\u2013709 (2004)"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045, 314\u2013318 (1998)","journal-title":"Journal of the ACM"},{"key":"22_CR11","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-33996-7_16","volume-title":"Algorithmic Game Theory","author":"P.W. Goldberg","year":"2012","unstructured":"Goldberg, P.W., McCabe, A.: Commodity auctions and frugality ratios. In: Serna, M. (ed.) SAGT 2012. LNCS, vol.\u00a07615, pp. 180\u2013191. Springer, Heidelberg (2012)"},{"issue":"4","key":"22_CR13","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econometrica\u00a041(4), 617\u2013631 (1973)","journal-title":"Econometrica"},{"issue":"1","key":"22_CR14","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/S0097539704444750","volume":"35","author":"R. Hassin","year":"2005","unstructured":"Hassin, R., Levin, A.: A better-than-greedy approximation algorithm for the minimum set cover problem. SIAM Journal on Computing\u00a035(1), 189\u2013200 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"22_CR15","first-page":"317","volume":"1","author":"V. Kann","year":"1994","unstructured":"Kann, V.: Polynomially bounded minimization problems that are hard to approximate. Nord. J. Comput.\u00a01(3), 317\u2013331 (1994)","journal-title":"Nord. J. Comput."},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Kempe, D., Tamir, T.: Beyond VCG: Frugality of truthful mechanisms. In: Procs. of 46th FOCS, pp. 615\u2013626 (2005)","DOI":"10.1109\/SFCS.2005.25"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Kempe, D., Salek, M., Moore, C.: Frugal and truthful auctions for vertex covers, flows and cuts. In: Procs. of 51st FOCS, pp. 745\u2013754 (2010)","DOI":"10.1109\/FOCS.2010.76"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511800481"},{"key":"22_CR19","unstructured":"Phillips, R.: Pricing and Revenue Optimization. Stanford University Press (1995)"},{"issue":"1","key":"22_CR20","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1509\/jmkg.66.1.55.18455","volume":"66","author":"S. Stremersch","year":"2000","unstructured":"Stremersch, S., Tellis, G.J.: Strategic Bundling of Products and Prices: A New Synthesis for Marketing. Journal of Marketing\u00a066(1), 55\u201372 (2000, 2002)","journal-title":"Journal of Marketing"},{"key":"22_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/3-540-36494-3_53","volume-title":"STACS 2003","author":"K. Talwar","year":"2003","unstructured":"Talwar, K.: The price of truth: Frugality in truthful mechanisms. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 608\u2013619. Springer, Heidelberg (2003)"},{"issue":"1","key":"22_CR22","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W. Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance\u00a016(1), 8\u201337 (1961)","journal-title":"The Journal of Finance"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38233-8_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T10:09:41Z","timestamp":1746007781000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38233-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382321","9783642382338"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38233-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}