The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Lorsqu'un magasin vend des articles à des clients, il souhaite déterminer les prix des articles afin de maximiser son profit. Intuitivement, si le magasin vend des articles à des prix bas (resp. élevés), les clients achètent plus (resp. moins) d’articles, ce qui génère moins de profit pour le magasin. Il serait donc difficile pour le magasin de décider des prix des articles. Supposons que le magasin dispose d'un ensemble V of n articles et il y a un ensemble E of m clients qui souhaitent acheter ces articles, et supposent également que chaque article i ∈ V a le coût de production di et chaque client ej ∈ E a la valorisation vj sur le paquet ej ⊆ V d'articles. Quand le magasin vend un article i ∈ V au prix ri, le bénéfice pour l'article i is pi=ri-di. Le but du magasin est de décider du prix de chaque article afin de maximiser son profit total. Nous appelons ce problème de maximisation le prix des articles problème. Dans la plupart des travaux précédents, le problème de la tarification des articles a été considéré sous l'hypothèse que pi ≥ 0 pour chacun i ∈ V, cependant, Balcan et al. [Dans Proc. of WINE, LNCS 4858, 2007] a introduit la notion de « produit d'appel » et a montré que le vendeur peut obtenir un profit total plus important dans le cas où pi < 0 est autorisé que dans le cas où pi < 0 n'est pas autorisé. Dans cet article, nous dérivons des réductions préservant l'approximation parmi plusieurs problèmes de tarification d'articles et montrons que tous ont des algorithmes avec un bon rapport d'approximation.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Ryoso HAMANE, Toshiya ITOH, Kouhei TOMITA, "Approximation Preserving Reductions among Item Pricing Problems" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 149-157, February 2009, doi: 10.1587/transinf.E92.D.149.
Abstract: 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 i ∈ V has the production cost di and each customer ej ∈ E has the valuation vj on the bundle ej ⊆ V of items. When the store sells an item i ∈ V 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 i ∈ V, 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.149/_p
Copier
@ARTICLE{e92-d_2_149,
author={Ryoso HAMANE, Toshiya ITOH, Kouhei TOMITA, },
journal={IEICE TRANSACTIONS on Information},
title={Approximation Preserving Reductions among Item Pricing Problems},
year={2009},
volume={E92-D},
number={2},
pages={149-157},
abstract={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 i ∈ V has the production cost di and each customer ej ∈ E has the valuation vj on the bundle ej ⊆ V of items. When the store sells an item i ∈ V 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 i ∈ V, 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.},
keywords={},
doi={10.1587/transinf.E92.D.149},
ISSN={1745-1361},
month={February},}
Copier
TY - JOUR
TI - Approximation Preserving Reductions among Item Pricing Problems
T2 - IEICE TRANSACTIONS on Information
SP - 149
EP - 157
AU - Ryoso HAMANE
AU - Toshiya ITOH
AU - Kouhei TOMITA
PY - 2009
DO - 10.1587/transinf.E92.D.149
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - 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 i ∈ V has the production cost di and each customer ej ∈ E has the valuation vj on the bundle ej ⊆ V of items. When the store sells an item i ∈ V 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 i ∈ V, 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.
ER -