2013 | OriginalPaper | Buchkapitel
New Results on the Online Pricing Problem
verfasst von : Xiangzhong Xiang
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the online pricing problem where there are
m
identical items on sale and a sequence of users
u
1
,
u
2
,… arrive one by one. Each
u
i
has a non-increasing acceptable price function
ϕ
i
(·) where
ϕ
i
(
x
) is the highest unit price
u
i
is willing to pay for
x
items. Upon the arrival of a user, the seller needs to decide the number of items to be sold to the user and at what price. The goal is to maximize the revenue of the seller, which is the sum of money paid by all users.
For the case when the items are divisible and can be sold fractionally, we improve the results of Zhang
et al.
[19]. We design a new deterministic algorithm
$\mathcal{D}_p$
-DIV and prove that it has competitive ratio
$O( \prod_{j=1}^{\log^* h - 1} \log^{(j)} h )$
where
h
is the highest unit price a user is willing to pay; our algorithm is substantially better than the
$O(h^{ 3 \log_2^{-1/2} h })$
-competitive algorithm of Zhang
et al.
We also prove that no randomized algorithm can do better than Ω(log
h
)-competitive.
For the case when items are indivisible, there is no known result. We show in this paper that any deterministic algorithm for this case must have competitive ratio at least Ω(
h
)-competitive. Then, we give the first competitive randomized algorithm
mathcalR
p
-indiv with competitive ratio
$O( \prod_{j=1}^{\log^* h - 1} \log^{(j)} h )$
. If
h
is known ahead of time, we can reduce the competitive ratio to
O
(log
h
). Besides, we prove that no randomized algorithm can do better than Ω(log
h
)-competitive.