Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation

Ryoso HAMANE; Toshiya ITOH

doi:10.1093/ietisy/e91-d.2.187

Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation

Ryoso HAMANE, Toshiya ITOH

Full Text Views

0

Cite this

Summary :

When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. 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. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j ∈ C wishes to buy a set e_j ⊆ V of items and assigns valuation w(e_j) ≥ 0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.

Publication: IEICE TRANSACTIONS on Information Vol.E91-D No.2 pp.187-199

Publication Date: 2008/02/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e91-d.2.187

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category: Approximation Algorithms

Cite this

Copy

Ryoso HAMANE, Toshiya ITOH, "Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation" in IEICE TRANSACTIONS on Information, vol. E91-D, no. 2, pp. 187-199, February 2008, doi: 10.1093/ietisy/e91-d.2.187.
Abstract: When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. 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. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j ∈ C wishes to buy a set e_j ⊆ V of items and assigns valuation w(e_j) ≥ 0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.2.187/_p

Copy

@ARTICLE{e91-d_2_187,
author={Ryoso HAMANE, Toshiya ITOH, },
journal={IEICE TRANSACTIONS on Information},
title={Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation},
year={2008},
volume={E91-D},
number={2},
pages={187-199},
abstract={When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. 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. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j ∈ C wishes to buy a set e_j ⊆ V of items and assigns valuation w(e_j) ≥ 0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.},
keywords={},
doi={10.1093/ietisy/e91-d.2.187},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation
T2 - IEICE TRANSACTIONS on Information
SP - 187
EP - 199
AU - Ryoso HAMANE
AU - Toshiya ITOH
PY - 2008
DO - 10.1093/ietisy/e91-d.2.187
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2008
AB - When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. 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. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j ∈ C wishes to buy a set e_j ⊆ V of items and assigns valuation w(e_j) ≥ 0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.
ER -