Approximate Submodularity in Network Design Problems

References

• Acimovic J, Graves SC (2015) Making better fulfillment decisions on the fly in an online retail environment. Manufacturing Service Oper. Management 17(1):34–51.Link, Google Scholar
• Ajayi T, Lee T, Schaefer A (2022) A note on the implications of approximate submodularity in discrete optimization. Optim. Lett. 1–26.Google Scholar
• Alaei S, Hajiaghayi MT, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. Proc. 13th ACM Conf. on Electronic Commerce 18–35.Google Scholar
• Asadpour A, Wang X, Zhang J (2020) Online resource allocation with limited flexibility. Management Sci. 66(2):642–666.Link, Google Scholar
• Baardman L, Boroujeni SB, Cohen-Hillel T, Panchamgam K, Perakis G (2020) Detecting customer trends for optimal promotion targeting. Manufacturing Service Oper. Management, ePub ahead of print October 6, https://doi.org/10.1287/msom.2020.0893.Link, Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Proc. Eur. Sympos. on Algorithms (Springer, Berlin), 253–264.Google Scholar
• Cachon G, Terwiesch C (2011) Matching Supply with Demand: An Introduction to Operations Management, 3rd ed. (McGraw-Hill, Ashland, OH).Google Scholar
• Chan TC, Letourneau D, Potter BG 2022. Sparse flexible design: A machine learning approach. Flexible Services Manufacturing J. 1–51.Google Scholar
• Chen AI, Graves Sc (2021) Item aggregation and column generation for online-retail inventory placement. Manufacturing Service Oper. Management 23(5):1062–1076.Link, Google Scholar
• Chen X, Zhang J, Zhou Y (2015) Optimal sparse designs for process flexibility via probabilistic expanders. Oper. Res. 63(5):1159–1176.Link, Google Scholar
• Chen X, Ma T, Zhang J, Zhou Y (2019) Optimal design of process flexibility for general production systems. Oper. Res. 67(2):516–531.Abstract, Google Scholar
• Chou MC, Geoffrey A Chua HZ (2014) On the performance of sparse process structures in partial postponement production systems. Oper. Res. 62(2):348–365.Link, Google Scholar
• Chou MC, Teo C-P, Zheng H (2008) Process flexibility: Design, evaluation, and applications. Flexible Service Manufacturing J. 20(1–2):59–94.Crossref, Google Scholar
• Chou MC, Chua GA, Teo C-P, Zheng H (2011) Process flexibility revisited: The graph expander and its applications. Oper. Res. 59(5):1090–1105.Link, Google Scholar
• Cornuejols G, Fisher ML, Nemhauser GL (1977) Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Sci. 23(8):789–810.Link, Google Scholar
• Das A, Kempe D (2011) Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. Preprint, submitted February 19, https://arxiv.org/abs/1102.3975.Google Scholar
• Das A, Kempe D (2018) Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. J. Machine Learn. Res. 19(1):74–107.Google Scholar
• Désir A, Goyal V, Wei Y, Zhang J (2016) Sparse process flexibility designs: Is the long chain really optimal? Oper. Res. 64(2):416–431.Link, Google Scholar
• DeValve L, Pekeč S, Wei Y (2020) A primal-dual approach to analyzing ATO systems. Management Sci. 66(11):5389–5407.Link, Google Scholar
• DeValve L, Wei Y, Di Wu RY (2021) Understanding the value of fulfillment flexibility in an online retailing environment. Manufacturing Service Oper. Management, ePub ahead of print July 12, https://doi.org/10.1287/msom.2021.0981.Link, Google Scholar
• Elenberg ER, Khanna R, Dimakis AG, Negahban S (2018) Restricted strong convexity implies weak submodularity. Ann. Statist. 46(6B):3539–3568.Crossref, Google Scholar
• Feige U (1998) A threshold of ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• Feng W, Wang C, Shen Z-JM (2017) Process flexibility design in heterogeneous and unbalanced networks: A stochastic programming approach. IISE Trans. 49(8):781–799.Crossref, Google Scholar
• Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions II. Polyhedral Combinatorics (Springer, Berlin), 73–87.Crossref, Google Scholar
• Gale D, Politof T (1981) Substitutes and complements in network flow problems. Discrete Appl. Math. 3(3):175–186.Crossref, Google Scholar
• Hammond JH, Raman A (1994) Sport Obermeyer, Ltd (Harvard Business School, Boston).Google Scholar
• Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2):274–296.Crossref, Google Scholar
• Jain K, Mahdian M, Markakis E, Saberi A, Vazirani VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6):795–824.Crossref, Google Scholar
• Jordan WC, Graves SC (1995) Principles on the benefits of manufacturing process flexibility. Management Sci. 41(4):577–594.Link, Google Scholar
• Khuller S, Moss A, Naor JS (1999) The budgeted maximum coverage problem. Inform. Processing Lett. 70(1):39–45.Crossref, Google Scholar
• Krause A, Golovin D (2014) Submodular function maximization. Tractability 3:71–104.Crossref, Google Scholar
• Levi R, Roundy RO, Shmoys DB (2006) Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res. 31(2):267–284.Link, Google Scholar
• Manshadi V, Rodilitz S (2022) Online policies for efficient volunteer crowdsourcing. Management Sci. 68(9):6572–6590.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
• Santoso T, Ahmed S, Goetschalckx M, Shapiro A (2005) A stochastic programming approach for supply chain network design under uncertainty. Eur. J. Oper. Res. 167(1):96–115.Crossref, Google Scholar
• Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2009) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Crossref, Google Scholar
• Simchi-Levi D (2010) Operations Rules: Delivering Customer Value through Flexible Operations (MIT Press, Cambridge, MA).Google Scholar
• Simchi-Levi D, Wei Y (2012) Understanding the performance of the long chain and sparse designs in process flexibility. Oper. Res. 60(5):1125–1141.Link, Google Scholar
• Simchi-Levi D, Wei Y (2015) Worst-case analysis of process flexibility designs. Oper. Res. 63(1):166–185.Link, 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
• Topkis DM (2011) Supermodularity and Complementarity (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Wang S, Wang X, Zhang J (2021) A review of flexible processes and operations. Production Oper. Management 30(6):1804–1824.Google Scholar
• Wang S, Wang X, Zhang J (2022) Robust optimization approach to process flexibility designs with contribution margin differentials. Manufacturing Service Oper. Management 24(1):632–646.Google Scholar
• Wang X, Zhang J (2015) Process flexibility: A distribution-free bound on the performance of k-chain. Oper. Res. 63(3):555–571.Link, Google Scholar
• Wolsey LA (1982) Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Math. Oper. Res. 7(3):410–425.Link, Google Scholar
• Xu Z, Zhang H, Zhang J, Zhang RQ (2020) Online demand fulfillment under limited flexibility. Management Sci. 66(10):4667–4685.Link, Google Scholar
• Yan Z, Gao SY, Teo CP (2018) On the design of sparse but efficient structures in operations. Management Sci. 64(7):3421–3445.Link, Google Scholar