TY - GEN
T1 - Approximation and competitive algorithms for single-minded selling problem
AU - Chin, Francis Y.L.
AU - Poon, Sheung Hung
AU - Ting, Hing Fung
AU - Xu, Dachuan
AU - Yu, Dongxiao
AU - Zhang, Yong
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2018.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85058456353&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-04618-7_9
DO - 10.1007/978-3-030-04618-7_9
M3 - Conference contribution
AN - SCOPUS:85058456353
SN - 9783030046170
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 98
EP - 110
BT - Algorithmic Aspects in Information and Management - 12th International Conference, AAIM 2018, Proceedings
A2 - Butenko, Sergiy
A2 - Tang, Shaojie
A2 - Du, Ding-Zhu
A2 - Woodruff, David
PB - Springer Verlag
T2 - 12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018
Y2 - 3 December 2018 through 4 December 2018
ER -