Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem

  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 2015)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9198))

Included in the following conference series:

  • 1366 Accesses

Abstract

This paper provides a technique for designing truthful mechanisms for a combinatorial optimization problem, which requires composition algorithms. We show that the composition algorithm \(A\circ B\) is monotone if the algorithm A and the algorithm B are both monotone. Then, we apply this technique to the two-dimensional orthogonal knapsack problem with provable approximation bounds, improving the previous results in [5].

D. Ye—Research was supported in part by China Scholarship Council.

G. Zhang—Research was supported by NSFC(11271325).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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–82. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  2. Archer, A., Tardos, É.: Truthful mechanisms for one-parameter agents. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 482–491 (2001)

    Google Scholar 

  3. Archer, A.F.: Mechanisms for discrete optimization with rational agents. Ph.D. thesis, Cornell University (2004)

    Google Scholar 

  4. 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–619. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  5. Babaioff, M., Blumrosen, L.: Computationally-feasible truthful auctions for convex bundles. Games and Economic Behavior 63(2), 588–620 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bougeret, M., Dutot, P.-F., Jansen, K., Otte, C., Trystram, D.: A fast 5/2-approximation algorithm for hierarchical scheduling. In: D’Ambra, P., Guarracino, M., Talia, D. (eds.) Euro-Par 2010, Part I. LNCS, vol. 6271, pp. 157–167. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  7. 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–327. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  8. 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–48. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  9. Bougeret, M., Dutot, P.F., Trystram, D.: An extention of the 5/2-approximation algorithm using oracle. Research Report (2010)

    Google Scholar 

  10. Briest, P., Krysta, P., Vöcking, B.: Approximation techniques for utilitarian mechanism design. SIAM Journal on Computing 40(6), 1587–1622 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  11. Caprara, A., Kellerer, H., Pferschy, U.: The multiple subset sum problem. SIAM Journal on Optimization 11, 308–319 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  12. 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–69. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  13. Chekuri, C., Khanna, S.: On multi-dimensional packing problems. In: Proceedings of the 10th annual ACM-SIAM symposium on Discrete Algorithms (SODA), pp. 185–194 (1999)

    Google Scholar 

  14. Christodoulou, G., Kovács, A.: A deterministic truthful ptas for scheduling related machines. In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1005–1016 (2010)

    Google Scholar 

  15. 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–826 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  16. 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–24 (2008)

    Google Scholar 

  17. 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–784 (2010)

    Google Scholar 

  18. 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–12 (2008)

    MATH  MathSciNet  Google Scholar 

  19. 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–584 (2010)

    Google Scholar 

  20. Jansen, K.: Parameterized approximation scheme for the multiple knapsack problem. SIAM Journal on Computing 39, 1392–1412 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  21. Jansen, K., Zhang, G.: Maximizing the total profit of rectangles packed into a rectangle. Algorithmica 47(3), 323–342 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  22. 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–62. Springer, Heidelberg (1999)

    Google Scholar 

  23. Kulik, A., Shachnai, H.: There is no eptas for two-dimensional knapsack. Information Processing Letters 110(16), 707–710 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  24. Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. Journal of the ACM 58(6), 25 (2011)

    Article  MathSciNet  Google Scholar 

  25. Lehmann, D., Oćallaghan, L.I., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM (JACM) 49(5), 577–602 (2002)

    Article  Google Scholar 

  26. Mu’Alem, A., Nisan, N.: Truthful approximation mechanisms for restricted combinatorial auctions. Games and Economic Behavior 64(2), 612–631 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  27. Nisan, N., Ronen, A.: Algorithmic mechanism design. In: Proceedings of the thirty-first annual ACM Symposium on Theory of Computing (STOC), pp. 129–140 (1999)

    Google Scholar 

  28. Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing 26, 401–409 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  29. Ye, D., Han, X., Zhang, G.: Online multiple-strip packing. Theoretical Computer Science 412(3), 233–239 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  30. 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–236. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  31. Zhuk, S.: Approximate algorithms to pack rectangles into several strips. Discrete Mathematics and Applications 16(1), 73–85 (2006)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Computer Science, Zhejiang University, Hangzhou, 310027, China

    Deshi Ye & Guochuan Zhang

Authors
  1. Deshi Ye
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guochuan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Deshi Ye .

Editor information

Editors and Affiliations

  1. Beijing University of Technology, Beijing, China

    Dachuan Xu

  2. University of New Brunswick, Fredericton, Canada

    Donglei Du

  3. University of Texas at Dallas, Richardson, USA

    Dingzhu Du

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Ye, D., Zhang, G. (2015). Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem. In: Xu, D., Du, D., Du, D. (eds) Computing and Combinatorics. COCOON 2015. Lecture Notes in Computer Science(), vol 9198. Springer, Cham. https://doi.org/10.1007/978-3-319-21398-9_31

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-21398-9_31

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-21397-2

  • Online ISBN: 978-3-319-21398-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation