{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T21:10:02Z","timestamp":1748466602936,"version":"3.41.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_31","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"390-401","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem"],"prefix":"10.1007","author":[{"given":"Deshi","family":"Ye","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guochuan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"31_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-540-31856-9_6","volume-title":"STACS 2005","author":"N Andelman","year":"2005","unstructured":"Andelman, N., Azar, Y., Sorani, M.: Truthful approximation mechanisms for scheduling selfish related machines. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 69\u201382. Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 482\u2013491 (2001)","key":"31_CR2","DOI":"10.1109\/SFCS.2001.959924"},{"unstructured":"Archer, A.F.: Mechanisms for discrete optimization with rational agents. Ph.D. thesis, Cornell University (2004)","key":"31_CR3"},{"key":"31_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-540-24749-4_53","volume-title":"STACS 2004","author":"V Auletta","year":"2004","unstructured":"Auletta, V., De Prisco, R., Penna, P., Persiano, G.: Deterministic truthful approximation mechanisms for scheduling related machines. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 608\u2013619. Springer, Heidelberg (2004)"},{"issue":"2","key":"31_CR5","doi-asserted-by":"publisher","first-page":"588","DOI":"10.1016\/j.geb.2006.07.002","volume":"63","author":"M Babaioff","year":"2008","unstructured":"Babaioff, M., Blumrosen, L.: Computationally-feasible truthful auctions for convex bundles. Games and Economic Behavior 63(2), 588\u2013620 (2008)","journal-title":"Games and Economic Behavior"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-642-15277-1_16","volume-title":"Euro-Par 2010 - Parallel Processing","author":"M Bougeret","year":"2010","unstructured":"Bougeret, M., Dutot, P.-F., Jansen, K., Otte, C., Trystram, D.: A fast 5\/2-approximation algorithm for hierarchical scheduling. In: D\u2019Ambra, P., Guarracino, M., Talia, D. (eds.) Euro-Par 2010, Part I. LNCS, vol. 6271, pp. 157\u2013167. Springer, Heidelberg (2010)"},{"key":"31_CR7","series-title":"IFIP Advances in Information and Communication Technology","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/978-3-642-15240-5_23","volume-title":"Theoretical Computer Science","author":"M Bougeret","year":"2010","unstructured":"Bougeret, M., Dutot, P.F., Jansen, K., Otte, C., Trystram, D.: Approximating the non-contiguous multiple organization packing problem. In: Calude, C.S., Sassone, V. (eds.) TCS 2010. IFIP AICT, vol. 323, pp. 316\u2013327. Springer, Heidelberg (2010)"},{"key":"31_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-12450-1_4","volume-title":"Approximation and Online Algorithms","author":"M Bougeret","year":"2010","unstructured":"Bougeret, M., Dutot, P.F., Jansen, K., Otte, C., Trystram, D.: Approximation algorithms for multiple strip packing. In: Bampis, E., Jansen, K. (eds.) WAOA 2009. LNCS, vol. 5893, pp. 37\u201348. Springer, Heidelberg (2010)"},{"unstructured":"Bougeret, M., Dutot, P.F., Trystram, D.: An extention of the 5\/2-approximation algorithm using oracle. Research Report (2010)","key":"31_CR9"},{"issue":"6","key":"31_CR10","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 Journal on Computing 40(6), 1587\u20131622 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1137\/S1052623498348481","volume":"11","author":"A Caprara","year":"2000","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: The multiple subset sum problem. SIAM Journal on Optimization 11, 308\u2013319 (2000)","journal-title":"SIAM Journal on Optimization"},{"key":"31_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-642-03685-9_5","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"C Chekuri","year":"2009","unstructured":"Chekuri, C., Gamzu, I.: Truthful mechanisms via greedy iterative packing. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. LNCS, vol. 5687, pp. 56\u201369. Springer, Heidelberg (2009)"},{"unstructured":"Chekuri, C., Khanna, S.: On multi-dimensional packing problems. In: Proceedings of the 10th annual ACM-SIAM symposium on Discrete Algorithms (SODA), pp. 185\u2013194 (1999)","key":"31_CR13"},{"doi-asserted-by":"crossref","unstructured":"Christodoulou, G., Kov\u00e1cs, A.: A deterministic truthful ptas for scheduling related machines. In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1005\u20131016 (2010)","key":"31_CR14","DOI":"10.1137\/1.9781611973075.81"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"EG Coffman","year":"1980","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level oriented two-dimensional packing algorithms. SIAM Journal on Computing 9, 808\u2013826 (1980)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Dhangwatnotai, P., Dobzinski, S., Dughmi, S., Roughgarden, T.: Truthful approximation schemes for single-parameter agents. In: Proceedings of 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 15\u201324 (2008)","key":"31_CR16","DOI":"10.1109\/FOCS.2008.71"},{"doi-asserted-by":"crossref","unstructured":"Dughmi, S., Roughgarden, T.: Black-box randomized reductions in algorithmic mechanism design. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 775\u2013784 (2010)","key":"31_CR17","DOI":"10.1109\/FOCS.2010.79"},{"issue":"1","key":"31_CR18","first-page":"1","volume":"3","author":"AV Fishkin","year":"2008","unstructured":"Fishkin, A.V., Gerber, O., Jansen, K., Solis-Oba, R.: On packing rectangles with resource augmentation: Maximizing the profit. Algorithmic Operations Research 3(1), 1\u201312 (2008)","journal-title":"Algorithmic Operations Research"},{"doi-asserted-by":"crossref","unstructured":"Grandoni, F., Krysta, P., Leonardi, S., Ventre, C.: Utilitarian mechanism design for multi-objective optimization. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 573\u2013584 (2010)","key":"31_CR19","DOI":"10.1137\/1.9781611973075.48"},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"1392","DOI":"10.1137\/080731207","volume":"39","author":"K Jansen","year":"2009","unstructured":"Jansen, K.: Parameterized approximation scheme for the multiple knapsack problem. SIAM Journal on Computing 39, 1392\u20131412 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"31_CR21","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00453-006-0194-5","volume":"47","author":"K Jansen","year":"2007","unstructured":"Jansen, K., Zhang, G.: Maximizing the total profit of rectangles packed into a rectangle. Algorithmica 47(3), 323\u2013342 (2007)","journal-title":"Algorithmica"},{"key":"31_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-540-48413-4_6","volume-title":"Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques","author":"H Kellerer","year":"1999","unstructured":"Kellerer, H.: A polynomial time approximation scheme for the multiple knapsack problem. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol. 1671, pp. 51\u201362. Springer, Heidelberg (1999)"},{"issue":"16","key":"31_CR23","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/j.ipl.2010.05.031","volume":"110","author":"A Kulik","year":"2010","unstructured":"Kulik, A., Shachnai, H.: There is no eptas for two-dimensional knapsack. Information Processing Letters 110(16), 707\u2013710 (2010)","journal-title":"Information Processing Letters"},{"issue":"6","key":"31_CR24","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/2049697.2049699","volume":"58","author":"R Lavi","year":"2011","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. Journal of the ACM 58(6), 25 (2011)","journal-title":"Journal of the ACM"},{"issue":"5","key":"31_CR25","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1145\/585265.585266","volume":"49","author":"D Lehmann","year":"2002","unstructured":"Lehmann, D., O\u0107allaghan, L.I., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM (JACM) 49(5), 577\u2013602 (2002)","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"31_CR26","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1016\/j.geb.2007.12.009","volume":"64","author":"A Mu\u2019Alem","year":"2008","unstructured":"Mu\u2019Alem, A., Nisan, N.: Truthful approximation mechanisms for restricted combinatorial auctions. Games and Economic Behavior 64(2), 612\u2013631 (2008)","journal-title":"Games and Economic Behavior"},{"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 (STOC), pp. 129\u2013140 (1999)","key":"31_CR27","DOI":"10.1145\/301250.301287"},{"key":"31_CR28","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A Steinberg","year":"1997","unstructured":"Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing 26, 401\u2013409 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"31_CR29","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/j.tcs.2009.09.029","volume":"412","author":"D Ye","year":"2011","unstructured":"Ye, D., Han, X., Zhang, G.: Online multiple-strip packing. Theoretical Computer Science 412(3), 233\u2013239 (2011)","journal-title":"Theoretical Computer Science"},{"key":"31_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-642-29952-0_25","volume-title":"Theory and Applications of Models of Computation","author":"D Ye","year":"2012","unstructured":"Ye, D., Zhang, G.: Coordination mechanisms for selfish parallel jobs scheduling - (extended abstract). In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol. 7287, pp. 225\u2013236. Springer, Heidelberg (2012)"},{"issue":"1","key":"31_CR31","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1515\/156939206776241264","volume":"16","author":"S Zhuk","year":"2006","unstructured":"Zhuk, S.: Approximate algorithms to pack rectangles into several strips. Discrete Mathematics and Applications 16(1), 73\u201385 (2006)","journal-title":"Discrete Mathematics and Applications"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T20:34:05Z","timestamp":1748464445000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}