Optimal Selection of Customers for a Last-Minute Offer

Roberto Cominetti (), José R. Correa (), Thomas Rothvoß () and Jaime San Martín ()
Additional contact information
Roberto Cominetti: Departamento de Ingeniería Matemática, Universidad de Chile, Santiago, Chile
José R. Correa: Departamento de Ingeniería Industrial, Universidad de Chile, Santiago, Chile
Thomas Rothvoß: Institute of Mathematics EPFL, Lausanne, Switzerland
Jaime San Martín: Departamento de Ingeniería Matemática and Centro de Modelamiento Matemático, Universidad de Chile, Santiago, Chile

Operations Research, 2010, vol. 58, issue 4-part-1, 878-888

Abstract: We analyze a short-term revenue optimization problem involving the targeting of customers for a promotion in which a finite number of perishable items are sold on a last-minute offer. The goal is to select the subset of customers to whom the offer will be made available in order to maximize the expected return. Each client replies with a certain probability and reports a specific value that might depend on the customer type, so that the selected subset has to balance the risk of not selling all items with the risk of assigning an item to a low value customer.We show that threshold strategies , which select all those clients with values above a certain optimal threshold, might fail to achieve the maximal revenue. However, using a linear programming relaxation, we prove that they attain a constant factor of the optimal value. Specifically, the achieved factor is 1/2 when a single item is to be sold and approaches 1 as the number of available items grows to infinity. Also, for the single item case, we propose an upper bound based on a sharper linear relaxation that allows us to obtain a threshold strategy achieving at least 2/3 of the optimal revenue. Moreover, although the complexity status of the problem is open, we provide a polynomial time approximation scheme for the single item case.

Keywords: promotional sale; linear programming relaxations; approximation algorithms (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1090.0787 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:878-888

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().