The search functionality is under construction.

The search functionality is under construction.

When a store sells items to customers, the store wishes to decide the prices of 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 the items, and also assume that each item *i* ∈ *V* has the production cost *d*_{i} and each customer *e*_{j} ∈ *E* has the valuation *v*_{j} on the bundle *e*_{j} ⊆ *V* of items. When the store sells an item *i* ∈ *V* at the price *r*_{i}, the profit for the item *i* is *p*_{i}=*r*_{i}-*d*_{i}. 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 *p*_{i} ≥ 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 *p*_{i} < 0 is allowed than in the case that *p*_{i} < 0 is not allowed. In this paper, we consider the line highway problem (in which each customer is interested in an interval on the line of the items) and the cycle highway problem (in which each customer is interested in an interval on the cycle of the items), and show approximation algorithms for the line highway problem and the cycle highway problem in which the smallest valuation is *s* and the largest valuation is *s*,

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1779-1786

- Publication Date
- 2009/08/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E92.A.1779

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category
- Theory

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.

Copy

Ryoso HAMANE, Toshiya ITOH, Kouhei TOMITA, "Approximation Algorithms for the Highway Problem under the Coupon Model" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 8, pp. 1779-1786, August 2009, doi: 10.1587/transfun.E92.A.1779.

Abstract: When a store sells items to customers, the store wishes to decide the prices of 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 the items, and also assume that each item *i* ∈ *V* has the production cost *d*_{i} and each customer *e*_{j} ∈ *E* has the valuation *v*_{j} on the bundle *e*_{j} ⊆ *V* of items. When the store sells an item *i* ∈ *V* at the price *r*_{i}, the profit for the item *i* is *p*_{i}=*r*_{i}-*d*_{i}. 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 *p*_{i} ≥ 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 *p*_{i} < 0 is allowed than in the case that *p*_{i} < 0 is not allowed. In this paper, we consider the line highway problem (in which each customer is interested in an interval on the line of the items) and the cycle highway problem (in which each customer is interested in an interval on the cycle of the items), and show approximation algorithms for the line highway problem and the cycle highway problem in which the smallest valuation is *s* and the largest valuation is *s*,

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1779/_p

Copy

@ARTICLE{e92-a_8_1779,

author={Ryoso HAMANE, Toshiya ITOH, Kouhei TOMITA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Approximation Algorithms for the Highway Problem under the Coupon Model},

year={2009},

volume={E92-A},

number={8},

pages={1779-1786},

abstract={When a store sells items to customers, the store wishes to decide the prices of 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 the items, and also assume that each item *i* ∈ *V* has the production cost *d*_{i} and each customer *e*_{j} ∈ *E* has the valuation *v*_{j} on the bundle *e*_{j} ⊆ *V* of items. When the store sells an item *i* ∈ *V* at the price *r*_{i}, the profit for the item *i* is *p*_{i}=*r*_{i}-*d*_{i}. 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 *p*_{i} ≥ 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 *p*_{i} < 0 is allowed than in the case that *p*_{i} < 0 is not allowed. In this paper, we consider the line highway problem (in which each customer is interested in an interval on the line of the items) and the cycle highway problem (in which each customer is interested in an interval on the cycle of the items), and show approximation algorithms for the line highway problem and the cycle highway problem in which the smallest valuation is *s* and the largest valuation is *s*,

keywords={},

doi={10.1587/transfun.E92.A.1779},

ISSN={1745-1337},

month={August},}

Copy

TY - JOUR

TI - Approximation Algorithms for the Highway Problem under the Coupon Model

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1779

EP - 1786

AU - Ryoso HAMANE

AU - Toshiya ITOH

AU - Kouhei TOMITA

PY - 2009

DO - 10.1587/transfun.E92.A.1779

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E92-A

IS - 8

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - August 2009

AB - When a store sells items to customers, the store wishes to decide the prices of 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 the items, and also assume that each item *i* ∈ *V* has the production cost *d*_{i} and each customer *e*_{j} ∈ *E* has the valuation *v*_{j} on the bundle *e*_{j} ⊆ *V* of items. When the store sells an item *i* ∈ *V* at the price *r*_{i}, the profit for the item *i* is *p*_{i}=*r*_{i}-*d*_{i}. 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 *p*_{i} ≥ 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 *p*_{i} < 0 is allowed than in the case that *p*_{i} < 0 is not allowed. In this paper, we consider the line highway problem (in which each customer is interested in an interval on the line of the items) and the cycle highway problem (in which each customer is interested in an interval on the cycle of the items), and show approximation algorithms for the line highway problem and the cycle highway problem in which the smallest valuation is *s* and the largest valuation is *s*,

ER -