{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:48:31Z","timestamp":1743072511986,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_21","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"221-233","source":"Crossref","is-referenced-by-count":5,"title":["Bounding the Payment of Approximate Truthful Mechanisms"],"prefix":"10.1007","author":[{"given":"Gruia","family":"Calinescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","unstructured":"Archer, A., Papadimitriou, C., Talwar, K., Tardos, E.: An Approximate Truthful Mechansim for Combinatorial Auctions with Single Parameter Agents. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 205\u2013214 (2003)"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, E.: Truthful Mechanisms for One-Parameter Agents. In: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, pp. 482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"key":"21_CR3","unstructured":"Archer, A., Tardos, E.: Frugal path mechanisms. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 991\u2013999 (2002)"},{"key":"21_CR4","unstructured":"Baudis, G., Gropl, C., Hougardy, S., Nierhoff, T., Promel, H.J.: Approximating minimum spanning sets in hypergraphs and polymatroids. In: ICALP (2000)"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1006\/jagm.1994.1041","volume":"17","author":"P. Berman","year":"1994","unstructured":"Berman, P., Ramaiyer, V.: Improved Approximations for the Steiner Tree Problem. J. Algorithms\u00a017, 381\u2013408 (1994)","journal-title":"J. Algorithms"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Bikhchandani, S., de Vries, S., Schummer, J., Vohra, R.: Linear programming and Vickrey auctions. In: IMA Volumes in Mathematics and its Applications, Mathematics of the Internet: E-Auctions and Markets, vol.\u00a0127, pp. 75\u2013116 (2001)","DOI":"10.1007\/978-1-4684-9277-4_6"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0196-6774(92)90018-8","volume":"13","author":"P.M. Camerini","year":"1992","unstructured":"Camerini, P.M., Galbiati, G., Maffioli, F.: Random pseudo-polynomial algorithms for exact matroid problems. J. Algorithms\u00a013, 258\u2013273 (1992)","journal-title":"J. Algorithms"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set covering problem. Mathematics of Operation Research\u00a04, 233\u2013235 (1979)","journal-title":"Mathematics of Operation Research"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Clarke, E.H.: Multipart pricing of public goods. In: Public Choice, vol.\u00a08, pp. 17\u201333 (1971)","DOI":"10.1007\/BF01726210"},{"key":"21_CR10","volume-title":"Combinatorial Optimization","author":"W.J. Cook","year":"1998","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley-Interscience, Hoboken (1998)"},{"key":"21_CR11","unstructured":"Elkind, E., Sahai, A., Steiglitz, K.: Frugality in path auctions. In: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 701\u2013709 (2004)"},{"issue":"4","key":"21_CR12","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentive in teams. Econometrica\u00a041(4), 617\u2013631 (1973)","journal-title":"Econometrica"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Helgason, T.: Aspects of the theory of hypermatroids. In: Hypergraph Seminar: Ohio State University, pp. 191\u2013213 (1974)","DOI":"10.1007\/BFb0066195"},{"key":"21_CR14","unstructured":"Hougardy, S., Promel, H.J.: A 1.598 approximation algorithm for the Steiner problem in graphs. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 448\u2013453 (1999)"},{"key":"21_CR15","unstructured":"Karpinski, M., Zelikovsky, A.: New Approximation Algorithms for the Steiner Tree Problems. In: Electronic Colloquium on Computational Complexity (ECCC), vol.\u00a02(030) (1995)"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Li, X.-Y., Wang, W.: Efficient Strategyproof Multicast in Selfish Networks. In: International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks (2004)","DOI":"10.1201\/9780203323687.ch5"},{"key":"21_CR17","unstructured":"Lovasz, L.: Flats in matroids and geometric graphs. In: Sixth British combinatorial conference, pp. 45\u201386 (1977)"},{"key":"21_CR18","volume-title":"Microeconomic Theory","author":"A. Mas-Colle","year":"1995","unstructured":"Mas-Colle, A., Whinston, W., Green, J.: Microeconomic Theory. Oxford university press, Oxford (1995)"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"McDiamid, C.: Rado\u2019s theorem for polymatroids. In: Math. Proc. Cambridge Philos. Soc., vol.\u00a078, pp. 263\u2013281 (1975)","DOI":"10.1017\/S0305004100051677"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. In: Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 129\u2013140 (1999)","DOI":"10.1145\/301250.301287"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.: Algorithms, games, and the Internet. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 749\u2013753 (2001)","DOI":"10.1145\/380752.380883"},{"key":"21_CR22","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/jagm.2000.1086","volume":"36","author":"H.J. Promel","year":"2000","unstructured":"Promel, H.J., Steger, A.: A new approximation algorithm for the Steiner tree problem with performance ratio 5\/3. J. of Algorithms\u00a036, 89\u2013101 (2000)","journal-title":"J. of Algorithms"},{"key":"21_CR23","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner Tree Approximation in Graphs. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 770\u2013779 (2000)"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Ronen, A.: Algorithms For Rational Agents. In: SOFSEM (2000)","DOI":"10.1007\/3-540-44411-4_5"},{"key":"21_CR25","doi-asserted-by":"crossref","unstructured":"Talwar, K.: The price of truth: Frugality in truthful mechanisms. In: 20 th Annual Symposium on Theoretical Aspects of Computer Science, pp. 608\u2013619 (2003)","DOI":"10.1007\/3-540-36494-3_53"},{"key":"21_CR26","doi-asserted-by":"publisher","first-page":"8","DOI":"10.2307\/2977633","volume":"16","author":"W. Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculation, auctions and competitive sealed tenders. Journal of Finance\u00a016, 8\u201337 (1961)","journal-title":"Journal of Finance"},{"key":"21_CR27","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Analysis of the greedy algorithm for the submodular set covering problem. Combinatorica\u00a02, 385\u2013392 (1982)","journal-title":"Combinatorica"},{"key":"21_CR28","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A. Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An 11\/6-Approximation Algorithm for the Network Steiner Tree Problem. Algorithmica\u00a09, 463\u2013470 (1993)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T21:52:21Z","timestamp":1740261141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}