Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems | SpringerLink
Skip to main content
Springer Nature Link
Log in

Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems

  • Conference paper
Algorithms and Computation (ISAAC 2006)

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

Included in the following conference series:

  • 1221 Accesses

Abstract

We study the interval knapsack problem (I-KP), and the interval multiple-choice knapsack problem (I-MCKP), as generalizations of the classic 0/1 knapsack problem (KP) and the multiple-choice knapsack problem (MCKP), respectively. Compared to singleton items in KP and MCKP, each item i in I-KP and I-MCKP is represented by a ([a i , b i ], p i ) pair, where integer interval [a i , b i ] specifies the possible range of units, and p i is the unit-price. Our main results are a FPTAS for I-KP with time O(n logn + n/ε 2) and a FPTAS for I-MCKP with time O(nm /ε), and pseudo-polynomial-time algorithms for both I-KP and I-MCKP with time O(nM) and space O(n + M). Here n, m, and M denote number of items, number of item sets, and knapsack capacity respectively. We also present a 2-approximation of I-KP and a 3-approximation of I-MCKP both in linear time.

We apply I-KP and I-MCKP to the single-good multi-unit sealed-bid auction clearing problem where M identical units of a single good are auctioned. We focus on two bidding models, among them the interval model allows each bid to specify an interval range of units, and XOR-interval model allows a bidder to specify a set of mutually exclusive interval bids. The interval and XOR-interval bidding models correspond to I-KP and I-MCKP respectively, thus are solved accordingly. We also show how to compute VCG payments to all the bidders with an overhead of O(logn) factor. Our results for XOR-interval bidding model imply improved algorithms for the piecewise constant bidding model studied by Kothari et al. [18], improving their algorithms by a factor of Ω(n).

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

Access this chapter

Log in via an institution

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. Davenport, J.K.A., Lee, H.: Computational aspects of clearing continuous call double auctions with assignment constraints and indivisible demand. Electronic Commerce Research 1(3), 221–238 (2001)

    Article  MATH  Google Scholar 

  2. Briest, P., Krysta, P., Vcking, B.: Approximation techniques for utilitarian mechanism design. In: Proc. STOC, pp. 39–48 (2005)

    Google Scholar 

  3. Chandra, A.K., Hirschberg, D.S., Wong, C.: Approximate algorithms for some generalized knapsack problems. Theoretical Computer Science 3, 293–304 (1976)

    Article  MathSciNet  Google Scholar 

  4. Dang, V.D., Jennings, N.R.: Optimal clearing algorithms for multi-unit single-item and multi-unit combinatorial auctions with demand/supply function bidding. In: Proc. 5th ICEC, pp. 25–30 (2003)

    Google Scholar 

  5. Dyer, M.E.: An O(n) algorithm for the multiple-choice knapsack linear program. Mathematical Programming 29, 57–63 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  6. Eso, M., Ghosh, S., Kalagnanam, J., Ladanyi, L.: Bid evaluation in procurement auctions with piecewise linear supply curves. J. Heuristics 11(2), 147–173 (2005)

    Article  MATH  Google Scholar 

  7. Gajewska, H., Tarjan, R.E.: Deques with heap order. Information Processing Letters 22(4), 197–200 (1986)

    Article  Google Scholar 

  8. Gens, G.V., Levner, E.V.: Approximation algorithms for certain universal problems in scheduling theory. Soviet J. Comput. System Sci. 6, 31–36 (1978)

    Google Scholar 

  9. Holte, R.C.: Combinatorial auctions, knapsack problems, and hill-climbing search. In: Stroulia, E., Matwin, S. (eds.) Canadian AI 2001. LNCS (LNAI), vol. 2056, pp. 57–66. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  10. Hood, R., Melville, R.: Real-time queue operations in pure LISP. Information Processing Letters 13, 50–54 (1981)

    Article  Google Scholar 

  11. Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM 22, 463–468 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  12. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

    Google Scholar 

  13. Kellerer, H., Pferschy, U.: A new fully polynomial time approximation scheme for the knapsack problem. J. of Comb. Opt. 3(1), 59–71 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  14. Kellerer, H., Pferschy, U.: Improved dynamic programming in connection with an FPTAS for the knapsack problem. J. of Comb. Opt. 8(1), 5–11 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  15. Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)

    MATH  Google Scholar 

  16. Kelly, F., Steinberg, R.: A combinatorial auction with multiple winners for universal services. Management Science 46, 586–596 (2000)

    Article  Google Scholar 

  17. Kelly, T.P.: Generalized knapsack solvers for multi-unit combinatorial auctions. In: Faratin, P., Rodríguez-Aguilar, J.-A. (eds.) AMEC 2004. LNCS (LNAI), vol. 3435, Springer, Heidelberg (2006)

    Google Scholar 

  18. Kothari, A., Parkes, D.C., Suri, S.: Approximately-strategyproof and tractable multi-unit auctions. Decision Support Systems 39, 105–121 (2005)

    Article  Google Scholar 

  19. Kothari, A., Suri, S., Zhou, Y.: Interval subset-sum and uniform-price auction clearing. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 608–620. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  20. Lawler, E.L.: Fast approximation algorithms for knapsack problems. Mathematics of Operations Research 4, 339–356 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  21. Lehmann, D., O’Callaghan, L.I., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. In: Proc. ACM EC, pp. 96–102 (1999)

    Google Scholar 

  22. Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic Behavior 35, 166–196 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  23. Rothkopf, M.H., Pekec, A., Harstad, R.M.: Computationally manageable combinatorial auctions. Management Science 44(8), 1131–1147 (1998)

    Article  MATH  Google Scholar 

  24. Sandholm, T.: Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence 135(1-2), 1–54 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  25. Sandholm, T., Suri, S.: Market clearability. In: IJCAI, pp. 1145–1151 (2001)

    Google Scholar 

  26. Walsh, W.E., Wellman, M.P., Ygge, F.: Combinatorial auctions for supply chain formation. In: Proc. ACM EC, pp. 260–269 (2000)

    Google Scholar 

  27. Zemel, E.: An O(n) algorithm for the linear multiple choice knapsack problem and related problems. Information Processing Letters 18, 123–128 (1984)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. HP Labs, 1501 Page Mill Rd, Palo Alto, CA, 94304, USA

    Yunhong Zhou

Authors
  1. Yunhong Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Japan Advanced Institute of Science and Technology, Japan

    Tetsuo Asano

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Zhou, Y. (2006). Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_50

Download citation

  • DOI: https://doi.org/10.1007/11940128_50

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-49694-6

  • Online ISBN: 978-3-540-49696-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics