| 講演名 | 2007-04-26 商品価格設定問題に対する近似アルゴリズム 浜根 良壮, 伊東 利哉, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 商品に対する顧客の購入可能金額(見積り価格)が既知であるとする.このとき,売り手が商品の価格を高く設定すると,顧客は商品の購入を控えるため,売り手の利益は減少する.一方,売り手が商品の価格を安く設定すると,顧客は商品を積極的に購入するが商品あたりの利益が減少するため,売り手の利益は減少する.このように,各商品に対する顧客の購入可能金額(見積り金額)が既知である場合に,売り手が自らの利益を最大化するように商品の価格設定を行なう問題を"商品価格設定問題"という.商品価格設定問題については,その状況-各商品の供給量が有限(あるいは無限)であるか,各顧客が個別に特定(あるいは不特定)の商品群の購入を希望するか-に応じて,さまざまな問題設定が可能となる.BalcanとBlumは,各商品の供給量が無限であり,各顧客が個別に特定の商品群の購入を希望する場合の商品価格設定問題をグラフにより定式化し,効率的な近似アルゴリズムを構成するとともにその近似比の解析を行った.本論文では,入力グラフの最大次数や顧客の最大見積もり価格比に注目することにより,各商品の供給量が無限であり,各顧客が個別に特定の商品群の購入を希望する場合の商品価格設定問題に大して新しい近似アルゴリズムを提案し,本論文で提案するアルゴリズムが良好な近似比を有することを示す. |
| 抄録(英) | 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, hte customers buys more (resp. less) items, which provides less profit to the store. So it whould be hard for the store to decide the prices of items. Assume that a storeshas a set V of n items and there is a set C of m coutomers 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 problem according to how many items the store can sell and how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as an unlimited supply model (resp. a limited supply model). The item pricing problem is said to be single-minded if each customer j ∈ C wishes to buy a set ej ⊆ V of items and assigns its valiation w(ej) >___ 0. Balcan and Blum regarde the single-minded item pricing problems (in unlimited supply model) as weighted k-hypertraphs and described several approximation algorithms. Tn this paper, we consider the maximum (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 unlimited supply item pricing problems, we show improved approximation algorithms w.r.t. the maximum (pseudo)degree and the valuation ratio. |
| キーワード(和) | 商品価格付け / 近似アルゴリズム / 次数制限 / 希望購入価格制限 |
| キーワード(英) | Item Pricing / Approximation Algorithm / Pseudodegree / Valuation Ratio |
| 資料番号 | COMP2007-1 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2007/4/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 商品価格設定問題に対する近似アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Improved Approximation Algorithms for Item Pricing with Bounded Degree and Valuation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 商品価格付け / Item Pricing |
| キーワード(2)（和/英） | 近似アルゴリズム / Approximation Algorithm |
| キーワード(3)（和/英） | 次数制限 / Pseudodegree |
| キーワード(4)（和/英） | 希望購入価格制限 / Valuation Ratio |
| 第 1 著者 氏名（和/英） | 浜根 良壮 / Ryoso HAMANE |
| 第 1 著者 所属（和/英） | 東京工業大学物理情報システム専攻 Dept. of Information Processing, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 伊東 利哉 / Toshiya ITOH |
| 第 2 著者 所属（和/英） | 東京工業大学学術国際情報センター GSIC, Tokyo institute of Technology |
| 発表年月日 | 2007-04-26 |
| 資料番号 | COMP2007-1 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 24 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |