Submodular Order Functions and Assortment Optimization

References

• Aouad A, Farias V, Levi R, Segev D (2018) The approximability of assortment optimization under ranking preferences. Oper. Res. 66(6):1661–1669.Link, Google Scholar
• Avadhanula V, Bhandari J, Goyal V, Zeevi A (2016) On the tightness of an lp relaxation for rational optimization and its applications. Oper. Res. Lett. 44(5):612–617.Crossref, Google Scholar
• Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. Proc. 25th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1497–1514.Google Scholar
• Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: Massive data summarization on the fly. Macskassy SA, Perlich C, Leskovec J, Wang W, Ghani R, eds. Proc. 20th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 671–680.Google Scholar
• Berbeglia G, Joret G (2020) Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments. Algorithmica 82(4):681–720.Crossref, Google Scholar
• Blanchet J, Gallego G, Goyal V (2016) A Markov chain approximation to choice modeling. Oper. Res. 64(4):886–905.Link, Google Scholar
• Bradley RA, Terry ME (1952) Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika 39:324.Google Scholar
• Calinescu G, Chekuri C, Pal M, Vondrák J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6):1740–1766.Crossref, Google Scholar
• Chakrabarti A, Kale S (2015) Submodular maximization meets streaming: Matchings, matroids, and more. Math. Programming 154(1):225–247.Crossref, Google Scholar
• Chekuri C, Gupta S, Quanrud K (2015) Streaming algorithms for submodular function maximization. Proc. Internat. Colloquium on Automata, Languages, and Programming (Springer, Berlin), 318–330.Google Scholar
• Das A, Kempe D (2011) Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. Getoor L, Scheffer T, eds. Proc. 28th Internat. Conf. Machine Learn. (Omnipress, Madison, WI), 1057–1064.Google Scholar
• Désir A, Goyal V, Zhang J (2021) Technical note—Capacitated assortment optimization: Hardness and approximation. Oper. Res. 70(2):893–904.Link, Google Scholar
• Désir A, Goyal V, Segev D, Ye C (2020) Constrained assortment optimization under the Markov chain–based choice model. Management Sci. 66(2):698–721.Link, Google Scholar
• Dobzinski S, Nisan N, Schapira M (2010) Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res. 35(1):1–13.Link, Google Scholar
• El Housni O, Topaloglu H (2023) Joint assortment optimization and customization under a mixture of multinomial logit models: On the value of personalized assortments. Oper. Res. 71(4):1197–1215.Link, Google Scholar
• Feige U, Mirrokni VS, Vondrak J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. Proc. IEEE 52nd Annual Sympos. on Foundations of Computer Sci. (IEEE, New York), 570–579.Google Scholar
• Feldman M, Norouzi-Fard A, Svensson O, Zenklusen R (2023) The one-way communication complexity of submodular maximization with applications to streaming and robustness. J. ACM 70(4):24:1–24:52.Google Scholar
• Feldman JB, Zhang DJ, Liu X, Zhang N (2022a) Customer choice models vs. machine learning: Finding optimal product displays on Alibaba. Oper. Res. 70(1):309–328.Google Scholar
• Feldman M, Liu P, Norouzi-Fard A, Svensson O, Zenklusen R (2022b) Streaming submodular maximization under matroid constraints. Bojańczyk M, Merelli E, Woodruff DP, eds. Proc. 49th Internat. Colloquium on Automata, Languages, and Programming, vol. 229 of Leibniz International Proceedings in Informatics (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 59:1–59:20.Google Scholar
• Filmus Y, Ward J (2012) A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. Proc. IEEE 53rd Annual Sympos. on Foundations of Computer Sci. (IEEE, New York), 659–668.Google Scholar
• Huang CC, Kakimura N (2021) Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica 83(3):879–902.Crossref, Google Scholar
• Jagabathula S (2014) Assortment optimization under general choice. Preprint, submitted October 21, https://dx.doi.org/10.2139/ssrn.2512831.Google Scholar
• Kök AG, Fisher ML, Vaidyanathan R (2008) Assortment planning: Review of literature and industry practice. Retail Supply Chain Management, 99–153.Google Scholar
• Krause A, Singh A, Guestrin C (2008a) Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. J. Machine. Learn. Res. 9(2):235–284.Google Scholar
• Krause A, McMahan HB, Guestrin C, Gupta A (2008b) Robust submodular observation selection. J. Machine Learn. Res. 9(12):2761–2801.Google Scholar
• Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. Berkhin P, Caruana R, Wu X, eds. Proc. 13th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 420–429.Google Scholar
• Luce RD (1959) Individual Choice Behavior: A Theoretical Analysis (Wiley, New York).Google Scholar
• McFadden D (1973) Conditional logit analysis of qualitative choice behavior. Zarembka P, ed. Frontiers in Econometrics (Academic Press, New York), 105–142.Google Scholar
• McFadden D, Train K (2000) Mixed MNL models for discrete response. J. Appl. Econometrics 15(5):447–470.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Plackett RL (1975) The analysis of permutations. J. Roy. Statist. Soc. Ser. C Appl. Statist. 24(2):193–202.Google Scholar
• Rusmevichientong P, Shen ZJM, Shmoys DB (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Oper. Res. 58(6):1666–1680.Link, Google Scholar
• Seshadhri C, Vondrák J (2014) Is submodularity testable? Algorithmica 69(1):1–25.Crossref, Google Scholar
• Sumida M, Gallego G, Rusmevichientong P, Topaloglu H, Davis J (2021) Revenue-utility tradeoff in assortment optimization under the multinomial logit model with totally unimodular constraints. Management Sci. 67(5):2845–2869.Google Scholar
• Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1):41–43.Crossref, Google Scholar
• Talluri K, Van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15–33.Link, Google Scholar
• Wei K, Iyer R, Bilmes J (2015) Submodularity in data subset selection and active learning. Bach FR, Blei DM, eds. Proc. Internat. Conf. on Machine Learn. (PMLR, New York), 1954–1963.Google Scholar