Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959966 | European Journal of Operational Research | 2017 | 10 Pages |
Abstract
We consider auctions of items that can be arranged in rows. Examples of such a setting appear in allocating pieces of land for real estate development, or seats in a theater or stadium. The objective is, given bids on subsets of items, to find a subset of bids that maximizes auction revenue (often referred to as the winner determination problem). We describe a dynamic programing algorithm which, for a k-row problem with connected and gap-free bids, solves the winner determination problem in polynomial time. We study the complexity for bids in a grid, complementing known results in literature. Additionally, we study variants of the geometrical winner determination setting. We provide a NP-hardness proof for the 2-row setting with gap-free bids. Finally, we extend this dynamic programing algorithm to solve the case where bidders submit connected, but not necessarily gap-free bids in a 2-row and a 3-row problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Bart Vangerven, Dries R. Goossens, Frits C.R. Spieksma,