Exact Implementation of Abstract MAC Layer via Carrier Sensing
文献类型：会议论文
| 作者 | Dongxiao Yu; Yong Zhang; Yuyao Huang; Hai Jin; Francis Lau |
| 出版日期 | 2018 |
| 会议日期 | 2018 |
| 英文摘要 | The problem of item selling with the objective of maximizing the revenue is studied. Given a seller with k types of items and n single- minded buyers, i.e., each buyer is only interested in a particular bundle of items, to maximize the revenue, the seller must carefully assign some amount of bundles to each buyer with respect to the buyer’s accepted price. Each buyer bi is associated with a value function vi(·) such that vi(x) is the accepted unit bundle price bi is willing to pay for x bundles. We show that the single-minded item selling problem is NP-hard. More- over, we give an O(√k)-approximation algorithm. For the online version, i.e., the buyers come one by one and the decision on each buyer must be made before the arrival of the next buyer, an O(√k · (log h + log k))- competitive algorithm is achieved, where h is the highest unit item price among all buyers. |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/14068]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 推荐引用方式 GB/T 7714 | Dongxiao Yu,Yong Zhang,Yuyao Huang,et al. Exact Implementation of Abstract MAC Layer via Carrier Sensing[C]. 见:. 2018. |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。