Maximizing a Class of Utility Functions Over the Vertices of a Polytope

References

• Ahmed S (2006) Convexity and decomposition of mean-risk stochastic programs. Math. Programming 106(3):433–446.Crossref, Google Scholar
• Ahmed S, Atamtürk A (2011) Maximizing a class of submodular utility functions. Math. Programming 128(1):149–169.Crossref, Google Scholar
• Ahmed S, Papageorgiou DJ (2013) Probabilistic set covering with correlations. Oper. Res. 61(2):438–452.Link, Google Scholar
• Alizadeh F, Goldfarb D (2003) Second-order cone programming. Math. Programming 95(1):3–51.Crossref, Google Scholar
• Atamtürk A, Bhardwaj A (2015) Supermodular covering knapsack polytope. Discrete Optim. 18:74–86.Crossref, Google Scholar
• Atamtürk A, Narayanan V (2008) Polymatroids and risk minimization in discrete optimization. Oper. Res. Lett. 36:618–622.Crossref, Google Scholar
• Atamtürk A, Narayanan V (2009) The submodular 0-1 knapsack polytope. Discrete Optim. 6(4):333–344.Crossref, Google Scholar
• Badanidiyuru A, Vondrák J (2014) Fast algorithms for maximizing submodular functions. Chekuri C, ed. Proc. Twenty-Fifth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’14 (SIAM, Philadelphia), 1497–1514.Crossref, Google Scholar
• Balcan M, Harvey NJA (2010) Learning submodular functions. CoRR abs/1008.2159.Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math. Programming 98(1):49–71.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bier VM, Nagaraj A, Abhichandani V (2005) Protection of simple series and parallel systems with components of different values. Reliability Engrg. System Safety 87(3):315–323.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
• Chong JK, Ho TH, Tang CS (2001) A modeling framework for category assortment planning. Manufacturing Service Oper. Management 3(3):191–210.Link, Google Scholar
• Dani V, Hayes TP, Kakade SM (2008) Stochastic linear optimization under bandit feedback. Servedio RA, Zhang T, eds. Proc. 21st Annual Conf. Learning Theory, COLT ’08 (Omnipress, Madison, WI), 355–366.Google Scholar
• Fisher M, Nemhauser G, Wolsey L (1978) An analysis of approximations for maximizing submodular set functions II. Balinski M, Hoffman A, eds. Polyhedral Combinatorics, Mathematical Programming Studies, Vol. 8 (Springer, Berlin), 73–87.Crossref, Google Scholar
• Gen M, Yun Y (2006) Soft computing approach for reliability optimization: State-of-the-art survey. Reliability Engrg. System Safety 91(9):1008–1026.Crossref, Google Scholar
• Goemans MX, Harvey NJA, Iwata S, Mirrokni VS (2009) Approximating submodular functions everywhere. Mathieu C, ed. Proc. Twentieth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’09, (SIAM, Philadelphia), 535–544.Crossref, Google Scholar
• Hausken K (2008) Strategic defense and attack for series and parallel reliability systems. Eur. J. Oper. Res. 186(2):856–881.Crossref, Google Scholar
• Kulik A, Shachnai H, Tamir T (2009) Maximizing submodular set functions subject to multiple linear constraints. Mathieu C, ed. Proc. Twentieth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’09 (SIAM, Philadelphia), 545–554.Crossref, Google Scholar
• Levitin G, Hausken K (2008) Protection vs. redundancy in homogeneous parallel systems. Reliability Engrg. System Safety 93(10):1444–1451.Crossref, Google Scholar
• Lobo MS, Vandenberghe L, Boyd S, Lebret H (1998) Applications of second-order cone programming. Linear Algebra and Its Appl. 284:193–228.Crossref, Google Scholar
• Megiddo N (1991) On finding primal- and dual-optimal bases. INFORMS J. Comput. 3(1):63–65.Link, Google Scholar
• Nahmias S (2001) Production and Operations Analysis (McGraw-Hill, New York).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
• Nemirovski A, Todd M (2008) Interior-point methods for optimization. Acta Numerica 17:191–234.Crossref, Google Scholar
• Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• Nesterov YE, Todd MJ (1998) Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8(2):324–364.Crossref, Google Scholar
• Rusmevichientong P, Tsitsiklis JN (2010) Linearly parameterized bandits. Math. Oper. Res. 35(2):395–411.Link, 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
• Sen A, Atamtürk A, Kaminsky P (2015) A conic integer programming approach to constrained assortment optimization under the mixed multinomial logit model. Research Report BCOL.15.06, IEOR, University of California–Berkeley.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
• Van Ryzin G, Mahajan S (1999) On the relationship between inventory costs and variety benefits in retail assortments. Management Sci. 45(11):1496–1509.Link, Google Scholar
• Vondrák J, Chekuri C, Zenklusen R (2011) Submodular function maximization via the multilinear relaxation and contention resolution schemes. Fortnow L, Vadhan SP, eds. Proc. 43rd Annual ACM Sympos. Theory Comput., STOC ’11 (ACM, New York),783–792.Crossref, Google Scholar