Online coupon consumption problem

Nowadays, it is popular that the dealer makes profits by selling a kind of discount coupons, which can be used as money to purchase commodities with total cost less than or equal to the face value of the coupon. We can purchase a coupon at a price of 0<s≤1 times its face value and the number of potential purchasable coupons is a given integer l. The customer has the option to buy the goods by cash completely or by a discount coupon. However, each piece of goods can only use one coupon and the coupon used must have enough balance for the goods. The objective is to minimize the total cost for purchasing all the goods. In this paper, we reduce the problem to a special bin packing model. We consider the online problems for all 0<s≤1 and 1≤l≤∞. We present optimal online algorithms for all 0<s≤1 when l=∞ and l=1. For 2≤l<∞, we give both a lower bound and an algorithm, and show the algorithm is optimal for l=2. A preliminary version of this paper appeared in the proceedings of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science. Y. Jiang supported by Natural Science Foundation of Zhejiang Province (Y605316). Z. Tan supported by Natural Science Foundation of China (10671177, 60021201).