IEICE Transactions on Information and Systems

IEICE Transactions on Information and Systems 2008 E91-D(2):187-199; doi:10.1093/ietisy/e91-d.2.187

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by HAMANE, R. Articles by ITOH, T. Search for Related Content Social Bookmarking          What's this?

Copyright © 2008 The Institute of Electronics, Information and Communication Engineers

Special Section on Foundations of Computer Science -- Papers -- Approximation Algorithms

Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation^*

Ryoso HAMANE¹ and Toshiya ITOH²

¹ The author is with the Department of Information Processing, Tokyo Institute of Technology, Tokyo, 152–8552 Japan. E-mail: hamane{at}dac.gsic.titech.ac.jp, ² The author is with the Global Scientific Information and Computing Center (GSIC), Tokyo Institute of Technology, Tokyo, 152–8552 Japan. E-mail: titoh{at}dac.gsic.titech.ac.jp

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.

Key Words: item pricing, approximation algorithm, pseudodegree, valuation ratio

---

Manuscript received April 2, 2007. Manuscript revised June 8, 2007.

^* Research supported in part by Japan Society of the Promotion of Science, Grant-in-Aid for Scientific Research on Priority Areas, 16092205, 2007.

Reference

[1] M. Balcan and A. Blum, "Approximation algorithms and online mechanisms for item pricing," Proc. 7th ACM Conference on Electronic Commerce, pp.29–35, 2006.

[2] P. Briest and P. Krysta, "Single-minded unlimited supply pricing on sparce instances," Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1093–1102, 2006.

[3] G. Even, O. Goldreich, M. Luby, N. Nisan, and B. Velikovi, "Efficient approximation of product distributions," Random Structure and Algorithms, vol.13, no.1, pp.1–16, 1998.

[4] V. Guruswami, J.D. Hartline, A.R. Karlin, D. Karger, C. Kenyon, and F. McSherry, "On profit-maximizing envy-free pricing," Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1164–1174, 2005.

[5] R. Motowani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

[6] M. Luby and A. Wigderson, "Pairwise independence and derandomization," UC Berkeley Technical Report: CSD-95-880, 1995.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by HAMANE, R. Articles by ITOH, T. Search for Related Content Social Bookmarking          What's this?