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 log n + 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(log n) factor. Our results for XOR-interval bidding model imply improved algorithms for the piecewise constant bidding model studied by Kothari et al.improving their algorithms by a factor of Ω(n).
展开▼
机译：我们研究间隔背包问题（I-KP）和间隔多项选择背包问题（I-MCKP），作为经典0/1背包问题（KP）和多项选择背包问题（MCKP）的推广，分别。与KP和MCKP中的单例项目相比，I-KP和I-MCKP中的每个项目i均由（[a_i，b_i]，p_i）对表示，其中整数间隔[a_i，b_i]指定了可能的单位范围， p_i是单价。我们的主要结果是时间为O（n log n + n /ε〜2）的I-KP的FPTAS和时间为O（nm /ε）的I-MCKP的FPTAS，以及两个I的伪多项式时间算法-KP和I-MCKP，时间为O（nM），空间为O（n + M）。在此，n，m和M分别表示项目数，项目集数和背包容量。我们还提出了线性时间中I-KP的2逼近和I-MCKP的3逼近。我们将I-KP和I-MCKP应用于单商品多单位密封式投标拍卖清算问题，在该问题中拍卖M个相同商品的同一商品。我们关注两种出价模型，其中间隔模型允许每个出价指定单位的间隔范围，而异或间隔模型允许出价者指定一组相互排斥的间隔出价。区间竞标模型和XOR区间竞标模型分别对应于I-KP和I-MCKP，因此相应地求解。我们还展示了如何计算开销为O（log n）因子的所有竞标者的VCG付款。我们的XOR间隔竞标模型结果暗示了Kothari等人研究的分段恒定竞标模型的改进算法，将其算法改进了Ω（n）。
展开▼
