Approximation Algorithms for the Highway Problem under the Coupon Model

Ryoso HAMANE; Toshiya ITOH; Kouhei TOMITA

doi:10.1587/transfun.E92.A.1779

Approximation Algorithms for the Highway Problem under the Coupon Model

Ryoso HAMANE, Toshiya ITOH, Kouhei TOMITA

Full Text Views

0

Cite this

Summary :

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 (this is called an [s,]-valuation setting) or all valuations are identical (this is called a single valuation setting).

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

Cite this

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 (this is called an [s,]-valuation setting) or all valuations are identical (this is called a single valuation setting).
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 (this is called an [s,]-valuation setting) or all valuations are identical (this is called a single valuation setting).},
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 (this is called an [s,]-valuation setting) or all valuations are identical (this is called a single valuation setting).
ER -