@article {IOPORT.02137326,
    author       = {Chen, Ning and Deng, Xiaotie and Sun, Xiaoming},
    title        = {On complexity of single-minded auction.},
    year         = {2004},
    journal      = {Journal of Computer and System Sciences},
    volume       = {69},
    number       = {4},
    issn         = {0022-0000},
    pages        = {675-687},
    publisher    = {Elsevier Science (Academic Press), San Diego, CA},
    doi          = {10.1016/j.jcss.2004.04.012},
    abstract     = {Summary: We consider complexity issues for a special type of combinatorial auctions, the single-minded auction, where every agent is interested in only one subset of the commodities. First, we present a matching bound on the communication complexity for the single-minded auction under a general communication model. Next, we prove that it is NP-hard to decide whether a Walrasian equilibrium exists in a single-minded auction. Finally, we establish a polynomial size duality theorem for the existence of a Walrasian equilibrium for the single-minded auction.},
    identifier   = {02137326},
}