Back to Search
Start Over
Multi-Stage and Multi-Customer Assortment Optimization With Inventory Constraints
- Source :
- SSRN Electronic Journal.
- Publication Year :
- 2019
- Publisher :
- Elsevier BV, 2019.
-
Abstract
- We consider an assortment optimization problem where a customer chooses a single item from a sequence of sets shown to her, while limited inventories constrain the items offered to customers over time. In the special case where all of the assortments have size one, our problem captures the online stochastic matching with timeouts problem. For this problem, we derive a polynomial-time approximation algorithm which earns at least 1-ln(2-1/e), or 0.51, of the optimum. This improves upon the previous-best approximation ratio of 0.46, and furthermore, we show that it is tight. For the general assortment problem, we establish the first constant-factor approximation ratio of 0.09 for the case that different types of customers value items differently, and an approximation ratio of 0.15 for the case that different customers value each item the same. Our algorithms are based on rounding an LP relaxation for multi-stage assortment optimization, and improve upon previous randomized rounding schemes to derive the tight ratio of 1-ln(2-1/e).
- Subjects :
- FOS: Computer and information sciences
Mathematical optimization
Sequence
Optimization problem
Computer science
Rounding
Value (computer science)
Approximation algorithm
Linear programming relaxation
Optimization and Control (math.OC)
Computer Science - Data Structures and Algorithms
FOS: Mathematics
Data Structures and Algorithms (cs.DS)
Special case
Randomized rounding
Mathematics - Optimization and Control
Subjects
Details
- ISSN :
- 15565068
- Database :
- OpenAIRE
- Journal :
- SSRN Electronic Journal
- Accession number :
- edsair.doi.dedup.....538c22a451b5010898346fc1973369e0