Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems
Improved Multi-unit Auction Clearing Algorithms with Interval (Multiple-Choice) Knapsack Problems
复制标题
改进的带区间（多项选择）背包问题的多单元拍卖清算算法
DOI：
10.1007/11940128_50
复制
发表时间：
2006
影响因子：
2.9
通讯作者：
Yunhong Zhou
中科院分区：
文献类型：
--
作者：
Yunhong Zhou
本文研究了区间背包问题（I-KP）和区间多项选择背包问题（I-MCKP），分别作为经典的0/1背包问题（KP）和多项选择背包问题（MCKP）的推广。与KP和MCKP中的单个项目相比，i -KP和i -MCKP中的每个项目i由（[ai, bi], pi）对表示，其中整数区间[ai， bi]指定可能的单位范围，pi是单价。我们的主要成果是时间为O（n logn + n/e2）的I-KP的FPTAS和时间为O（nm /e）的I-MCKP的FPTAS，以及时间为O（nm）和空间为O（n + M）的I-KP和I-MCKP的伪多项式时间算法。其中n、m、m分别表示物品数量、物品集数量和背包容量。我们还在线性时间内给出了I-KP的2逼近和I-MCKP的3逼近。
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 ([ai , bi], pi) pair, where integer interval [ai, bi] specifies the possible range of units, and pi is the unit-price. Our main results are a FPTAS for I-KP with time O(n logn + n/e2) and a FPTAS for I-MCKP with time O(nm /e), 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).