Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

References

• Abeliuk A, Berbeglia G, Cebrian M, Van Hentenryck P (2016) Assortment optimization under a multinomial logit model with position bias and social influence. 4OR 14(1):57–75.Crossref, Google Scholar
• Agrawal S, Ding Y, Saberi A, Ye Y (2010) Correlation robust stochastic optimization. Proc. 21st Annu. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1087–1096.Google Scholar
• Agrawal S, Zadimoghaddam M, Mirrokni V (2018) Proportional allocation: Simple, distributed, and diverse matching with high entropy. Proc. 30th Internat. Conf. Machine Learning, Proceedings of Machine Learning Research, vol. 80 (PMLR), 99–108.Google Scholar
• Alaei S, Makhdoumi A, Malekian A (2021) Maximizing sequence-submodular functions and its application to online advertising. Management Sci. 67(10):6030–6054.Link, Google Scholar
• Anand BN, Shachar R (2011) Advertising, the matchmaker. RAND J. Econom. 42(2):205–245.Crossref, Google Scholar
• Aouad A, Segev D (2021) Display optimization for vertically differentiated locations under multinomial logit preferences. Management Sci. 67(6):3519–3550.Link, Google Scholar
• Aouad A, Farias V, Levi R (2021) Assortment optimization under consider-then-choose choice models. Management Sci. 67(6):3368–3386.Link, Google Scholar
• Asadpour A, Bateni M, Bhawalkar K, Mirrokni VS (2019) Concise bid optimization strategies with multiple budget constraints. Management Sci. 65(12):5785–5812.Link, Google Scholar
• Balseiro SR, Feldman J, Mirrokni V, Muthukrishnan S (2014) Yield optimization of display advertising with ad exchange. Management Sci. 60(12):2859–2885.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
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends® Machine Learning 8(3-4):231–357.Crossref, Google Scholar
• Buchbinder N, Feldman M, Seffi J, Schwartz R (2015) A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5):1384–1402.Crossref, Google Scholar
• Calinescu G, Chekuri C, Pál 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
• Celis LE, Kapoor S, Salehi F, Vishnoi N (2019) Controlling polarization in personalization: An algorithmic framework. FAT*’19 Proc. Conf. Fairness Accountability Transparency (Association for Computing Machinery, New York) 160–169.Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. 2010 IEEE 51st Annu. Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 575–584.Google Scholar
• Chekuri C, Vondrák J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6):1831–1879.Crossref, Google Scholar
• Derakhshan M, Golrezaei N, Manshadi V, Mirrokni V (2018) Product ranking on online platforms. Preprint, submitted February 26, https://dx.doi.org/10.2139/ssrn.3130378.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
• Dwork C, Kumar R, Naor M, Sivakumar D (2001) Rank aggregation methods for the web. WWW’01 Proc. 10th Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 613–622.Google Scholar
• Farias VF, Jagabathula S, Shah D (2013) A nonparametric approach to modeling choice with limited data. Management Sci. 59(2):305–322.Link, Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4):1133–1153.Crossref, Google Scholar
• Feldman JB, Topaloglu H (2017) Revenue management under the Markov chain choice model. Oper. Res. 65(5):1322–1342.Link, Google Scholar
• Feldman M (2021) Guess free maximization of submodular and linear sums. Algorithmica 83(3):853–878.Crossref, Google Scholar
• Ferreira KJ, Parthasarathy S, Sekar S (2022) Learning to rank an assortment of products. Management Sci. 68(3):1828–1848.Link, Google Scholar
• Ford LR, Fulkerson DR (1958) Network flow and systems of representatives. Canad. J. Math. 10:78–84.Crossref, Google Scholar
• Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• Gallego G, Topaloglu H (2014) Constrained assortment optimization for the nested logit model. Management Sci. 60(10):2583–2601.Link, Google Scholar
• Gallego G, Li A, Truong V-A, Wang X (2020) Approximation algorithms for product framing and pricing. Oper. Res. 68(1):134–160.Link, Google Scholar
• Ghosh A, McAfee P, Papineni K, Vassilvitskii S (2009) Bidding for representative allocations for display advertising. Leonardi S, ed. 5th Internat. Workshop Internet Network Econom. WINE, Lecture Notes in Computer Science, vol. 5929 (Springer, Berlin), 208–219.Google Scholar
• Goyal V, Levi R, Segev D (2016) Near-optimal algorithms for the assortment planning problem under dynamic substitution and stochastic demand. Oper. Res. 64(1):219–235.Link, Google Scholar
• Hall P (1935) On representatives of subsets. J. London Math. Soc. 1(1):26–30.Crossref, Google Scholar
• Ho TH, Tang CS (1998) Product Variety Management: Research Advances, International Series in Operations Research and Management Science, vol. 10 (Springer Science & Business Media, New York).Crossref, Google Scholar
• Hoban PR, Bucklin RE (2015) Effects of Internet display advertising in the purchase funnel: Model-based insights from a randomized field experiment. J. Marketing Res. 52(3):375–393.Crossref, Google Scholar
• Honhon D, Gaur V, Seshadri S (2010) Assortment planning and inventory decisions under stockout-based substitution. Oper. Res. 58(5):1364–1379.Link, Google Scholar
• Ilvento C, Jagadeesan M, Chawla S (2020) Multi-category fairness in sponsored search auctions. FAT*’20 Proc. 2020 Conf. Fairness Accountability Transparency (Association for Computing Machinery, New York), 348–358.Google Scholar
• Jagabathula S, Rusmevichientong P (2017) A nonparametric joint assortment and price choice model. Management Sci. 63(9):3128–3145.Link, Google Scholar
• Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. KDD’03 Proc. Ninth ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 137–146.Google Scholar
• Khachiyan LG (1979) A polynomial algorithm in linear programming. Doklady Akademii Nauk 244:1093–1096.Google Scholar
• Kök AG, Fisher ML, Vaidyanathan R (2008) Assortment planning: Review of literature and industry practice. Agrawal N, Smith S, eds. Retail Supply Chain Management, International Series in Operations Research & Management Science, vol. 223 (Springer, Boston), 99–153.Google Scholar
• Krause A, Golovin D (2014) Submodular function maximization. Bordeaux L, Hamadi Y, Kohli P, eds. Tractability: Practical Approaches to Hard Problems (Cambridge University Press, Cambridge, UK), 71–104.Crossref, Google Scholar
• Lahaie S, Pennock DM (2007) Revenue analysis of a family of ranking rules for keyword auctions. EC’07 Proc. 8th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 50–56.Google Scholar
• Lancaster K (1990) The economics of product variety: A survey. Marketing Sci. 9(3):189–206.Link, Google Scholar
• Li H, Kannan PK (2014) Attributing conversions in a multichannel online marketing environment: An empirical model and a field experiment. J. Marketing Res. 51(1):40–56.Crossref, Google Scholar
• Liu Q, van Ryzin G (2008) On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2):288–310.Link, Google Scholar
• Manchanda P, Dubé J-P, Goh KY, Chintagunta PK (2006) The effect of banner advertising on Internet purchasing. J. Marketing Res. 43(1):98–108.Crossref, Google Scholar
• Mehrotra A, Celis LE, Vishnoi NK (2019) Toward controlling discrimination in online ad auctions. Proc. 36th Internat. Conf. Machine Learning, Proceedings of Machine Learning Research, vol. 97 (PMLR, Long Beach, CA).Google Scholar
• Mirrokni V, Schapira M, Vondrák J (2008) Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. EC’08 Proc. 9th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 70–77.Google Scholar
• Mitrovic M, Feldman M, Krause A, Karbasi A (2018) Submodularity on hypergraphs: From sets to sequences. Proc. 21st Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 84 (PMLR Press), 1177–1184.Google Scholar
• Mokhtari A, Hassani H, Karbasi A (2020) Stochastic conditional gradient methods: From convex minimization to submodular maximization. J. Machine Learning Res 21(1):4232–4280.Google Scholar
• Nemhauser GL, Wolsey LA, Fisher MA (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Program. 14(1):265–294.Crossref, Google Scholar
• Niazadeh R, Roughgarden T, Wang J (2018) Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. NIPS’18 Proc. 32nd Internat. Conf. Neural Inform. Processing Systems, Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Red Hook, NY), 9594–9604.Google Scholar
• Niazadeh R, Golrezaei N, Wang J, Susan F, Badanidiyuru A (2020) Online learning via offline greedy: Applications in market design and optimization. Preprint, submitted May 29, https://dx.doi.org/10.2139/ssrn.3613756.Google Scholar
• Radlinski F, Broder AZ, Ciccolo P, Gabrilovich E, Josifovski V, Riedel L (2008) Optimizing relevance and revenue in ad search: A query substitution approach. SIGIR’08 Proc. 31st Annu. Internat. ACM SIGIR Conf. Res. Development Inform. Retrieval (Association for Computing Machinery, New York), 403–410.Google Scholar
• Rusmevichientong P, Shen Z-JM, Shmoys DB (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Oper. Res. 58(6):1666–1680.Link, Google Scholar
• Sayedi A (2018) Real-time bidding in online display advertising. Marketing Sci. 37(4):553–568.Link, 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.Link, Google Scholar
• Sviridenko M, Vondrák J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4):1197–1218.Link, 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
• Topaloglu H (2013) Joint stocking and product offer decisions under the multinomial logit model. Production Oper. Management 22(5):1182–1199.Crossref, Google Scholar
• Tschiatschek S, Singla A, Krause A (2017) Selecting sequences of items via submodular maximization. Proc. of the 31st AAAI Conference on Artificial Intelligence, vol. 31 (AAAI Press, Palo Alto, CA), 2667–2673.Google Scholar
• Vondrák J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. STOC’08 Proc. Fortieth Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 67–74.Google Scholar
• Vondrák J, Chekuri C, Zenklusen R (2011) Submodular function maximization via the multilinear relaxation and contention resolution schemes. STOC’11 Proc. Forty-Third Annu. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 783–792.Google Scholar
• Zhu Y, Wang G, Yang J, Wang D, Yan J, Chen Z (2009) Revenue optimization with relevance constraint in sponsored search. ADKDD’09 Proc. 3rd ACM SIGKDD Workshop Data Mining Audience Intelligence Advertising (Association for Computing Machinery, New York), 55–60.Google Scholar