Offline and online algorithms for single-minded selling problem

Yong Zhang, Francis Y.L. Chin, Sheung Hung Poon, Hing Fung Ting, Dachuan Xu, Dongxiao Yu

Research output: Journal PublicationArticlepeer-review

3 Citations (Scopus)

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 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.

Original languageEnglish
Pages (from-to)15-22
Number of pages8
JournalTheoretical Computer Science
Volume821
DOIs
Publication statusPublished - 12 Jun 2020

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Offline and online algorithms for single-minded selling problem'. Together they form a unique fingerprint.

Cite this