Approximation and competitive algorithms for single-minded selling problem

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

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

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 v i (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. Moreover, 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.

Original languageEnglish
Title of host publicationAlgorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings
EditorsSergiy Butenko, Shaojie Tang, Ding-Zhu Du, David Woodruff
PublisherSpringer Verlag
Pages98-110
Number of pages13
ISBN (Print)9783030046170
DOIs
Publication statusPublished - 2018
Event12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018 - Dallas, United States
Duration: 3 Dec 20184 Dec 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11343 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018
Country/TerritoryUnited States
CityDallas
Period3/12/184/12/18

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

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

Cite this