{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:19:23Z","timestamp":1742401163473},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642036842"},{"type":"electronic","value":"9783642036859"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_5","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"56-69","source":"Crossref","is-referenced-by-count":16,"title":["Truthful Mechanisms via Greedy Iterative Packing"],"prefix":"10.1007","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]},{"given":"Iftah","family":"Gamzu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Hartline, J.D.: Knapsack auctions. In: 17th SODA, pp. 1083\u20131092 (2006)","DOI":"10.1145\/1109557.1109677"},{"key":"5_CR2","unstructured":"Andelman, N., Mansour, Y., Zhu, A.: Competitive queueing policies for qos switches. In: 14th SODA, pp. 761\u2013770 (2003)"},{"key":"5_CR3","unstructured":"Archer, A., Papadimitriou, C.H., Talwar, K., Tardos, \u00c9.: An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: 14th SODA, pp. 205\u2013214 (2003)"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/978-3-540-70575-8_68","volume-title":"Automata, Languages and Programming","author":"Y. Azar","year":"2008","unstructured":"Azar, Y., Gamzu, I.: Truthful unification framework for packing integer programs with choices. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 833\u2013844. Springer, Heidelberg (2008)"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Azar, Y., Gamzu, I., Gutner, S.: Truthful unsplittable flow for large capacity networks. In: 19th SPAA, pp. 320\u2013329 (2007)","DOI":"10.1145\/1248377.1248432"},{"key":"5_CR6","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-540-27821-4_3","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Babaioff","year":"2004","unstructured":"Babaioff, M., Blumrosen, L.: Computationally-feasible truthful auctions for convex bundles. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 27\u201338. Springer, Heidelberg (2004)"},{"key":"5_CR7","unstructured":"Babaioff, M., Lavi, R., Pavlov, E.: Mechanism design for single-value domains. In: 20th AAAI, pp. 241\u2013247 (2005)"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Lavi, R., Pavlov, E.: Single-value combinatorial auctions and implementation in undominated strategies. In: 17th SODA, pp. 1054\u20131063 (2006)","DOI":"10.1145\/1109557.1109674"},{"key":"5_CR9","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-540-24749-4_17","volume-title":"STACS 2004","author":"Y. Bartal","year":"2004","unstructured":"Bartal, Y., Chin, F.Y.L., Chrobak, M., Fung, S.P.Y., Jawor, W., Lavi, R., Sgall, J., Tich\u00fd, T.: Online competitive algorithms for maximizing weighted throughput of unit jobs. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 187\u2013198. Springer, Heidelberg (2004)"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi unit combinatorial auctions. In: 9th TARK, pp. 72\u201387 (2003)","DOI":"10.1145\/846241.846250"},{"key":"5_CR11","volume-title":"Algorithmic Game Theory","author":"L. Blumrosen","year":"2007","unstructured":"Blumrosen, L., Nisan, N.: Combinatorial auctions. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, ch.\u00a011. Cambridge University Press, Cambridge (2007)"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Briest, P., Krysta, P., V\u00f6cking, B.: Approximation techniques for utilitarian mechanism design. In: 37th STOC, pp. 39\u201348 (2005)","DOI":"10.1145\/1060590.1060597"},{"key":"5_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G. Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (Extended abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 182\u2013196. Springer, Heidelberg (2007)"},{"issue":"3","key":"5_CR14","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C. Chekuri","year":"2005","unstructured":"Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SICOMP\u00a035(3), 713\u2013728 (2005)","journal-title":"SICOMP"},{"issue":"2","key":"5_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.jda.2005.03.005","volume":"4","author":"F.Y.L. Chin","year":"2006","unstructured":"Chin, F.Y.L., Chrobak, M., Fung, S.P.Y., Jawor, W., Sgall, J., Tich\u00fd, T.: Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Discrete Algorithms\u00a04(2), 255\u2013276 (2006)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"5_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s00453-003-1025-6","volume":"37","author":"F.Y.L. Chin","year":"2003","unstructured":"Chin, F.Y.L., Fung, S.P.Y.: Online scheduling with partial job values: Does timesharing or randomization help? Algorithmica\u00a037(3), 149\u2013164 (2003)","journal-title":"Algorithmica"},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01726210","volume":"8","author":"E.H. Clarke","year":"1971","unstructured":"Clarke, E.H.: Multipart pricing of public goods. Public Choice\u00a08, 17\u201333 (1971)","journal-title":"Public Choice"},{"key":"5_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-540-79309-0_16","volume-title":"Algorithmic Game Theory","author":"R. Cole","year":"2008","unstructured":"Cole, R., Dobzinski, S., Fleischer, L.K.: Prompt mechanisms for online auctions. In: Monien, B., Schroeder, U.-P. (eds.) SAGT 2008. LNCS, vol.\u00a04997, pp. 170\u2013181. Springer, Heidelberg (2008)"},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Sundararajan, M.: On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In: 9th EC, pp. 38\u201347 (2008)","DOI":"10.1145\/1386790.1386798"},{"key":"5_CR20","unstructured":"Englert, M., Westermann, M.: Considering suppressed packets improves buffer management in qos switches. In: 18th SODA, pp. 209\u2013218 (2007)"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: Improving the factor of 1 - 1\/e. In: 47th FOCS, pp. 667\u2013676 (2006)","DOI":"10.1109\/FOCS.2006.14"},{"key":"5_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"M.L. Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions ii. Mathematical Programming Study\u00a08, 73\u201387 (1978)","journal-title":"Mathematical Programming Study"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: 17th SODA, pp. 611\u2013620 (2006)","DOI":"10.1145\/1109557.1109624"},{"key":"5_CR24","unstructured":"Goundan, P.R., Schulz, A.S.: Revisiting the greedy approach to submodular set function maximization (manuscript) (2007)"},{"issue":"4","key":"5_CR25","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econemetrica\u00a041(4), 617\u2013631 (1973)","journal-title":"Econemetrica"},{"key":"5_CR26","unstructured":"Hajek, B.: On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In: Conference on Information Sciences and Systems, pp. 434\u2013438 (2001)"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Kleinberg, R.D., Mahdian, M., Parkes, D.C.: Online auctions with re-usable goods. In: 6th EC, pp. 165\u2013174 (2005)","DOI":"10.1145\/1064009.1064027"},{"key":"5_CR28","unstructured":"Jenkyns, T.A.: The efficiency of the \u201cgreedy\u201d algorithm. In: 7th South Eastern Conference on Combinatorics, Graph Theory and Computing, pp. 341\u2013350 (1976)"},{"key":"5_CR29","unstructured":"Lavi, R., Nisan, N.: Online ascending auctions for gradually expiring items. In: 16th SODA, pp. 1146\u20131155 (2005)"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: 46th FOCS, pp. 595\u2013604 (2005)","DOI":"10.1109\/SFCS.2005.76"},{"issue":"5","key":"5_CR31","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1145\/585265.585266","volume":"49","author":"D.J. Lehmann","year":"2002","unstructured":"Lehmann, D.J., O\u2019Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. JACM\u00a049(5), 577\u2013602 (2002)","journal-title":"JACM"},{"key":"5_CR32","unstructured":"Li, F., Sethuraman, J., Stein, C.: Better online buffer management. In: 18th SODA, pp. 199\u2013208 (2007)"},{"key":"5_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/11841036_48","volume-title":"Algorithms \u2013 ESA 2006","author":"J. Mestre","year":"2006","unstructured":"Mestre, J.: Greedy in approximation algorithms. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 528\u2013539. Springer, Heidelberg (2006)"},{"key":"5_CR34","first-page":"612","volume":"64","author":"A. Mu\u2019alem","year":"2008","unstructured":"Mu\u2019alem, A., Nisan, N.: Truthful approximation mechanisms for restricted combinatorial auctions. GEB\u00a064, 612\u2013631 (2008)","journal-title":"GEB"},{"key":"5_CR35","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions i. Mathematical Programming\u00a014, 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"5_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N. Nisan","year":"2007","unstructured":"Nisan, N.: Introduction to mechanism design (for computer scientists). In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, ch.\u00a09. Cambridge University Press, Cambridge (2007)"},{"key":"5_CR37","first-page":"166","volume":"35","author":"N. Nisan","year":"2001","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. GEB\u00a035, 166\u2013196 (2001)","journal-title":"GEB"},{"key":"5_CR38","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1613\/jair.2046","volume":"29","author":"N. Nisan","year":"2007","unstructured":"Nisan, N., Ronen, A.: Computationally feasible vcg mechanisms. JAIR\u00a029, 19\u201347 (2007)","journal-title":"JAIR"},{"key":"5_CR39","volume-title":"Algorithmic Game Theory","author":"D.C. Parkes","year":"2007","unstructured":"Parkes, D.C.: Online mechanisms. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, ch.\u00a016. Cambridge University Press, Cambridge (2007)"},{"key":"5_CR40","doi-asserted-by":"crossref","unstructured":"Porter, R.: Mechanism design for online real-time scheduling. In: 5th EC, pp. 61\u201370 (2004)","DOI":"10.1145\/988772.988783"},{"key":"5_CR41","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W. Vickery","year":"1961","unstructured":"Vickery, W.: Counterspeculation, auctions and competitive sealed tender. Journal of Finance\u00a016, 8\u201337 (1961)","journal-title":"Journal of Finance"},{"key":"5_CR42","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: 40th STOC, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T03:34:09Z","timestamp":1558496049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}