کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959966 | 1445963 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Winner determination in geometrical combinatorial auctions
ترجمه فارسی عنوان
تعیین برنده در مزایده های ترکیبی هندسی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مزایده ها، برنامه ریزی پویا مشکل تعیین کننده برنده، پیچیدگی، ردیف
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 258, Issue 1, 1 April 2017, Pages 254-263
Journal: European Journal of Operational Research - Volume 258, Issue 1, 1 April 2017, Pages 254-263
نویسندگان
Bart Vangerven, Dries R. Goossens, Frits C.R. Spieksma,