Loading...
Please wait, while we are loading the content...
The Complexity and Algorithm for k-Duplicates Combinatorial Auctions with Submodular and Subadditive Bidders
| Content Provider | Semantic Scholar |
|---|---|
| Author | Chen, Wenbin Peng, Lingxi Wang, Jianxiong Xie, Dongqing Li, FuFang Tang, Maobin |
| Copyright Year | 2013 |
| Abstract | In this paper, we study the problem of maximizing welfare in combinatorial auctions with k(> 1)duplicates of each item, where k is a fixed constant (i.e. k is not the part of the input) and bidders are submodular or subadditive. We exhibit some upper and lower approximation bounds for k-duplicates combinatorial auctions. First, we show that it is NP-hard to approximate the maximum welfare for k-duplicates combinatorial auctions with subadditive bidders within a factor of 2− where > 0 unless P = NP . Secondly, we propose a 2-approximation algorithm for kduplicates combinatorial auctions with submodular bidders. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://weblidi.info.unlp.edu.ar/WorldComp2013-Mirror/p2013/FCS4161.pdf |
| Alternate Webpage(s) | http://worldcomp-proceedings.com/proc/p2013/FCS4161.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
