The search functionality is under construction.
The search functionality is under construction.

Approximation Preserving Reductions among Item Pricing Problems

Ryoso HAMANE, Toshiya ITOH, Kouhei TOMITA

  • Full Text Views

    0

  • Cite this

Summary :

When a store sells items to customers, the store wishes to determine the prices of the items to maximize its profit. Intuitively, if the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. So it would be hard for the store to decide the prices of items. Assume that the store has a set V of n items and there is a set E of m customers who wish to buy those items, and also assume that each item iV has the production cost di and each customer ejE has the valuation vj on the bundle ejV of items. When the store sells an item iV at the price ri, the profit for the item i is pi=ri-di. The goal of the store is to decide the price of each item to maximize its total profit. We refer to this maximization problem as the item pricing problem. In most of the previous works, the item pricing problem was considered under the assumption that pi ≥ 0 for each iV, however, Balcan, et al. [In Proc. of WINE, LNCS 4858, 2007] introduced the notion of "loss-leader," and showed that the seller can get more total profit in the case that pi < 0 is allowed than in the case that pi < 0 is not allowed. In this paper, we derive approximation preserving reductions among several item pricing problems and show that all of them have algorithms with good approximation ratio.

Publication
IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.149-157
Publication Date
2009/02/01
Publicized
Online ISSN
1745-1361
DOI
10.1587/transinf.E92.D.149
Type of Manuscript
Special Section PAPER (Special Section on Foundations of Computer Science)
Category

Authors

Keyword