Approximation Algorithms for the Highway Problem under the Coupon Model

Ryoso Hamane, Toshiya Itoh, Kouhei Tomita

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)…