IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v58y2010i4-part-1p878-888.html
   My bibliography  Save this article

Optimal Selection of Customers for a Last-Minute Offer

Author

Listed:
  • 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)

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.

Suggested Citation

  • Roberto Cominetti & José R. Correa & Thomas Rothvoß & Jaime San Martín, 2010. "Optimal Selection of Customers for a Last-Minute Offer," Operations Research, INFORMS, vol. 58(4-part-1), pages 878-888, August.
  • Handle: RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:878-888
    DOI: 10.1287/opre.1090.0787
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1090.0787
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.1090.0787?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Claude Chriqui & Pierre Robillard, 1975. "Common Bus Lines," Transportation Science, INFORMS, vol. 9(2), pages 115-121, May.
    2. Jan Roelf Bult & Tom Wansbeek, 1995. "Optimal Selection for Direct Mail," Marketing Science, INFORMS, vol. 14(4), pages 378-394.
    3. Loren K. Platzman & Jane C. Ammons & John J. Bartholdi, 1988. "A Simple and Efficient Algorithm to Compute Tail Probabilities from Transforms," Operations Research, INFORMS, vol. 36(1), pages 137-144, February.
    4. Brian C. Dean & Michel X. Goemans & Jan Vondrák, 2008. "Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 945-964, November.
    5. Michael O. Ball & Maurice Queyranne, 2009. "Toward Robust Revenue Management: Competitive Analysis of Online Booking," Operations Research, INFORMS, vol. 57(4), pages 950-963, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Huanan Zhang & Cong Shi & Chao Qin & Cheng Hua, 2016. "Stochastic regret minimization for revenue management problems with nonstationary demands," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 433-448, September.
    2. Tong, C.O. & Wong, S.C., 1998. "A stochastic transit assignment model using a dynamic schedule-based network," Transportation Research Part B: Methodological, Elsevier, vol. 33(2), pages 107-121, April.
    3. Xu, Zhandong & Xie, Jun & Liu, Xiaobo & Nie, Yu (Marco), 2020. "Hyperpath-based algorithms for the transit equilibrium assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    4. Paulsen, Mads & Rasmussen, Thomas Kjær & Nielsen, Otto Anker, 2021. "Impacts of real-time information levels in public transport: A large-scale case study using an adaptive passenger path choice model," Transportation Research Part A: Policy and Practice, Elsevier, vol. 148(C), pages 155-182.
    5. Wu, Di & Yin, Yafeng & Lawphongpanich, Siriphong, 2011. "Pareto-improving congestion pricing on multimodal transportation networks," European Journal of Operational Research, Elsevier, vol. 210(3), pages 660-669, May.
    6. Durango-Cohen, Elizabeth J., 2013. "Modeling contribution behavior in fundraising: Segmentation analysis for a public broadcasting station," European Journal of Operational Research, Elsevier, vol. 227(3), pages 538-551.
    7. Codina, Esteve & Rosell, Francisca, 2017. "A heuristic method for a congested capacitated transit assignment model with strategies," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 293-320.
    8. Adam J. Mersereau & Dan Zhang, 2012. "Markdown Pricing with Unknown Fraction of Strategic Customers," Manufacturing & Service Operations Management, INFORMS, vol. 14(3), pages 355-370, July.
    9. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    10. YongSeog Kim & W. Nick Street & Gary J. Russell & Filippo Menczer, 2005. "Customer Targeting: A Neural Network Approach Guided by Genetic Algorithms," Management Science, INFORMS, vol. 51(2), pages 264-276, February.
    11. Thomas J. Steenburgh & Andrew Ainslie & Peder Hans Engebretson, 2003. "Massively Categorical Variables: Revealing the Information in Zip Codes," Marketing Science, INFORMS, vol. 22(1), pages 40-57, August.
    12. Mahsa Samsami & Ralf Wagner, 2021. "Investment Decisions with Endogeneity: A Dirichlet Tree Analysis," JRFM, MDPI, vol. 14(7), pages 1-19, July.
    13. Martin Skutella & Maxim Sviridenko & Marc Uetz, 2016. "Unrelated Machine Scheduling with Stochastic Processing Times," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 851-864, August.
    14. repec:dgr:rugsom:02f59 is not listed on IDEAS
    15. Bas Donkers & Richard Paap & Jedid‐Jah Jonker & Philip Hans Franses, 2006. "Deriving target selection rules from endogenously selected samples," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 21(5), pages 549-562, July.
    16. Retsef Levi & Georgia Perakis & Joline Uichanco, 2015. "The Data-Driven Newsvendor Problem: New Bounds and Insights," Operations Research, INFORMS, vol. 63(6), pages 1294-1306, December.
    17. Wang, David Z.W. & Nayan, Ashish & Szeto, W.Y., 2018. "Optimal bus service design with limited stop services in a travel corridor," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 70-86.
    18. Roberto Cominetti & José Correa, 2001. "Common-Lines and Passenger Assignment in Congested Transit Networks," Transportation Science, INFORMS, vol. 35(3), pages 250-267, August.
    19. Belgacem Bouzaïene-Ayari & Michel Gendreau & Sang Nguyen, 2001. "Modeling Bus Stops in Transit Networks: A Survey and New Formulations," Transportation Science, INFORMS, vol. 35(3), pages 304-321, August.
    20. Homero Larrain & Juan Muñoz, 2008. "Public Transit Corridor Assignment Assuming Congestion Due to Passenger Boarding and Alighting," Networks and Spatial Economics, Springer, vol. 8(2), pages 241-256, September.
    21. Danijel Bratina & Armand Faganel, 2023. "Using Supervised Machine Learning Methods for RFM Segmentation: A Casino Direct Marketing Communication Case," Tržište/Market, Faculty of Economics and Business, University of Zagreb, vol. 35(1), pages 7-22.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:58:y:2010:i:4-part-1:p:878-888. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.