Technical Note—An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem

References

• Aouad A, Segev D (2020) Display optimization for vertically differentiated locations under Multinomial Logit preferences. Management Sci.67(6):3519–3550.Google Scholar
• Bai Y, Feldman J, Segev D, Topaloglu H, Wagner L (2021) Assortment optimization under the multi-purchase multinomial logit choice model. Preprint, submitted June 16, https://dx.doi.org/10.2139/ssrn.3866734.Google Scholar
• Bienstock D, Sethuraman J, Ye C (2013) Approximation algorithms for the incremental knapsack problem via disjunctive programming. Preprint, submitted November 18, https://arxiv.org/abs/1311.4563.Google Scholar
• Chekuri C, Khanna S (2005) A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3):713–728.Crossref, Google Scholar
• Davis JM, Topaloglu H, Williamson DP (2015) Assortment optimization over time. Oper. Res. Lett. 43(6):608–611.Crossref, Google Scholar
• Della Croce F, Pferschy U, Scatamacchia R (2018) Approximating the 3-period incremental knapsack problem. J. Discrete Algorithms 52–53:55–69.Crossref, Google Scholar
• Della Croce F, Pferschy U, Scatamacchia R (2019) On approximating the incremental knapsack problem. Discrete Appl. Math. 264:26–42.Crossref, Google Scholar
• Derakhshan M, Golrezaei N, Manshadi V, Mirrokni V (2022) Product ranking on online platforms. Management Sci., ePub ahead of print January 5, https://doi.org/10.1287/mnsc.2021.4044.Link, Google Scholar
• Faenza Y, Malinovic I (2018) A PTAS for the time-invariant incremental knapsack problem. Lee J, Rinaldi G, Mahjoub A, eds. Proc. 5th Internat. Sympos. on Combinatorial Optim., ISCO 2018. Lecture Notes in Computer Science, vol. 10856 (Springer, Cham), 157–169.Google Scholar
• Faenza Y, Segev D, Zhang L (2022) Approximation algorithms for the generalized incremental knapsack problem. Math. Program., https://doi.org/10.1007/s10107-021-01755-7.Google Scholar
• Feige U, Vondrák J (2010) The submodular welfare problem with demand queries. Theory Comput. 6(1):247–290.Crossref, Google Scholar
• Fleischer L, Goemans MX, Mirrokni VS, Sviridenko M (2011) Tight approximation algorithms for maximum separable assignment problems. Math. Oper. Res. 36(3):416–431.Link, Google Scholar
• Gallego G, Li A, Truong V, Wang X (2020) Approximation algorithms for product framing and pricing. Oper. Res. 68(1):134–160.Link, Google Scholar
• Hartline JRK (2008) Incremental optimization. PhD thesis, Department of Computer Science, Cornell University, Ithaca, NY.Google Scholar
• Hartline J, Sharp A (2006) An incremental model for combinatorial maximization problems. Proc. 5th Internat. Workshop on Experiment. Algorithms, 36–48.Google Scholar
• Ibarra OH, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4):463–468.Crossref, Google Scholar
• Jiang P, Feldman J (2021) Display optimization under the Multinomial Logit choice model: Balancing revenue and customer satisfaction. Preprint, submitted August 23, https://dx.doi.org/10.2139/ssrn.3909033.Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Complexity of Computer Computations (Springer, Berlin), 85–103.Crossref, Google Scholar
• Kellerer H, Pferschy U (1999) A new fully polynomial time approximation scheme for the knapsack problem. J. Combinatorial Optim. 3(1):59–71.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer-Verlag, Berlin).Crossref, Google Scholar
• Lawler EL (1979) Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4):339–356.Link, Google Scholar
• Magazine MJ, Oguz O (1981) A fully polynomial approximation algorithm for the 0-1 knapsack problem. Eur. J. Oper. Res. 8(3):270–273.Crossref, Google Scholar
• Sharp AM (2007) Incremental algorithms: Solving problems in a changing world. PhD thesis, Department of Computer Science, Cornell University, Ithaca, NY.Google Scholar
• Shmoys DB, Tardos É (1993) An approximation algorithm for the generalized assignment problem. Math. Programming 62:461–474.Crossref, Google Scholar
• Toth P, Martello S (1990) Knapsack Problems: Algorithms and Computer Implementations (Wiley, New York).Google Scholar
• Ye C (2016) On the trade-offs between modeling power and algorithmic complexity. PhD thesis, Department of Industrial Engineering and Operations Research, Columbia University, New York.Google Scholar