Approximation Algorithms for the Highway Problem under the Coupon Model

Details Approximation Algorithms for the Highway Problem under the Coupon Model Approximation Algorithms for the Highway Problem under the Coupon Model

2007-12-17

arxiv.org/abs/0712.2629v2

IEICE Trans. on Fundamentals, E92-A(8), pp.1779-1786, 2009

Computer Science

Data Structures and Algorithms

13 pages, 5 figures

Scientific paper

10.1587/transfun.E92.A.1779

When a store sells items to customers, the store wishes to determine the prices of the 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 those items, and also assume that each item i \in V has the production cost d_i and each customer e_j \in E has the valuation v_j on the bundle e_j \subseteq V of items. When the store sells an item i \in 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. In most of the previous works, the item pricing problem was considered under the assumption that p_i \geq 0 for each i \in 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 and the cycle highway problem, and show approximation algorithms for the line and/or cycle highway problem for which the smallest valuation is s and the largest valuation is \ell or all valuations are identical.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for the Highway Problem under the Coupon Model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for the Highway Problem under the Coupon Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for the Highway Problem under the Coupon Model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-115757