## Abstract

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 b_{i} is associated with a value function v_{i}(⋅) such that v_{i}(x) is the accepted unit bundle price b_{i} 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⋅(logh+logk))-competitive algorithm is given, where h is the highest unit item price among all buyers.

Original language | English |
---|---|

Pages (from-to) | 15-22 |

Number of pages | 8 |

Journal | Theoretical Computer Science |

Volume | 821 |

DOIs | |

Publication status | Published - 12 Jun 2020 |

## Keywords

- Approximation ratio
- Competitive ratio
- NP-hard
- Single-minded selling

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science (all)