Offline and online algorithms for single-minded selling problem

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 assign some amount of bundles to each buyer with respect to the buyer's accepted price. Each buyer bi is associated with...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2020-06, Vol.821, p.15-22
Main Authors: Zhang, Yong, Chin, Francis Y.L., Poon, Sheung-Hung, Ting, Hing-Fung, Xu, Dachuan, Yu, Dongxiao
Format: Article
Language:English
Subjects:
Approximation ratio
Competitive ratio
NP-hard
Single-minded selling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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. In this paper, we assume that bundles can be sold fractionally. The single-minded item selling problem is proved to be NP-hard. Moreover, we give an O(k)-approximation algorithm. For the online version, i.e., buyers come one by one and the decision must be made immediately on the arrival of each buyer, an O(k⋅(log⁡h+log⁡k))-competitive algorithm is given, where h is the highest unit item price among all buyers.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2020.03.017