{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T04:48:28Z","timestamp":1778906908413,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T00:00:00Z","timestamp":1650585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10107-022-01801-y","type":"journal-article","created":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T16:02:53Z","timestamp":1650643373000},"page":"69-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Sequence independent lifting for a set of submodular maximization problems"],"prefix":"10.1007","volume":"196","author":[{"given":"Xueyu","family":"Shi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oleg A.","family":"Prokopyev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8689-4281","authenticated-orcid":false,"given":"Bo","family":"Zeng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,22]]},"reference":[{"issue":"1\u20132","key":"1801_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-009-0298-1","volume":"128","author":"S Ahmed","year":"2011","unstructured":"Ahmed, S., Atamt\u00fcrk, A.: Maximizing a class of submodular utility functions. Math. Program. 128(1\u20132), 149\u2013169 (2011)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1801_CR2","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10107-015-0902-5","volume":"154","author":"A Angulo","year":"2015","unstructured":"Angulo, A., Espinoza, D., Palma, R.: Sequence independent lifting for mixed knapsack problems with gub constraints. Math. Program. 154(1\u20132), 55\u201380 (2015)","journal-title":"Math. Program."},{"issue":"3","key":"1801_CR3","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1287\/opre.1030.0099","volume":"52","author":"A Atamt\u00fcrk","year":"2004","unstructured":"Atamt\u00fcrk, A.: Sequence independent lifting for mixed-integer programming. Oper. Res. 52(3), 487\u2013490 (2004)","journal-title":"Oper. Res."},{"issue":"2","key":"1801_CR4","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1287\/opre.2016.1570","volume":"65","author":"A Atamt\u00fcrk","year":"2017","unstructured":"Atamt\u00fcrk, A., G\u00f3mez, A.: Maximizing a class of utility functions over the vertices of a polytope. Oper. Res. 65(2), 433\u2013445 (2017)","journal-title":"Oper. Res."},{"issue":"3","key":"1801_CR5","doi-asserted-by":"publisher","first-page":"1943","DOI":"10.1137\/15M1033009","volume":"27","author":"A Atamt\u00fcrk","year":"2017","unstructured":"Atamt\u00fcrk, A., K\u00fc\u00e7\u00fckyavuz, S., Tezel, B.: Path cover and path pack inequalities for the capacitated fixed-charge network flow problem. SIAM J. Optim. 27(3), 1943\u20131976 (2017)","journal-title":"SIAM J. Optim."},{"issue":"5","key":"1801_CR6","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1016\/j.orl.2008.04.006","volume":"36","author":"A Atamt\u00fcrk","year":"2008","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5), 618\u2013622 (2008)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"1801_CR7","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/j.disopt.2009.03.002","volume":"6","author":"A Atamt\u00fcrk","year":"2009","unstructured":"Atamt\u00fcrk, A., Narayanan, V.: The submodular knapsack polytope. Discret. Optim. 6(4), 333\u2013344 (2009)","journal-title":"Discret. Optim."},{"key":"1801_CR8","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Submodular functions maximization problems. In: Handbook of Approximation Algorithms and Metaheuristics, Second Edition, pp. 771\u2013806. CRC Press (2018)","DOI":"10.1201\/9781351236423-42"},{"key":"1801_CR9","unstructured":"Chen, W., Wang, Y., Yuan, Y.: Combinatorial multi-armed bandit: General framework and applications. In: International Conference on Machine Learning, pp. 151\u2013159 (2013)"},{"key":"1801_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer Programming. Springer, Berlin (2014)"},{"key":"1801_CR11","unstructured":"Dolhansky, B.W., Bilmes, J.A.: Deep submodular functions: Definitions and learning. In: Advances in Neural Information Processing Systems, pp. 3404\u20133412 (2016)"},{"key":"1801_CR12","doi-asserted-by":"crossref","unstructured":"El-Arini, K., Veda, G., Shahaf, D., Guestrin, C.: Turning down the noise in the blogosphere. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 289\u2013298. ACM (2009)","DOI":"10.1145\/1557019.1557056"},{"key":"1801_CR13","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Elsevier, Netherlands (2005)"},{"issue":"1","key":"1801_CR14","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1023\/A:1009841107478","volume":"4","author":"Z Gu","year":"2000","unstructured":"Gu, Z., Nemhauser, G.L., Savelsbergh, M.W.: Sequence independent lifting in mixed integer programming. J. Comb. Optim. 4(1), 109\u2013129 (2000)","journal-title":"J. Comb. Optim."},{"key":"1801_CR15","unstructured":"Gurobi\u00a0Optimization, L.: Gurobi optimizer reference manual (2019). http:\/\/www.gurobi.com"},{"key":"1801_CR16","doi-asserted-by":"crossref","unstructured":"Itoko, T., Iwata, S.: Computational geometric approach to submodular function minimization for multiclass queueing systems. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 267\u2013279. Springer (2007)","DOI":"10.1007\/978-3-540-72792-7_21"},{"key":"1801_CR17","doi-asserted-by":"crossref","unstructured":"K\u0131l\u0131n\u00e7-Karzan, F., K\u00fc\u00e7\u00fckyavuz, S., Lee, D.: Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens. Mathematical Programming pp. 1\u201344 (2021)","DOI":"10.1007\/s10107-021-01688-1"},{"key":"1801_CR18","doi-asserted-by":"crossref","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. In: Bordeaux, L., Hamadi, Y., Kohli, P. (eds.) Tractability: Practical Approaches to Hard Problems, pp. 71\u2013104. Cambridge University Press, Cambridge (2014)","DOI":"10.1017\/CBO9781139177801.004"},{"issue":"1","key":"1801_CR19","first-page":"354","volume":"44","author":"J Li","year":"2019","unstructured":"Li, J., Deshpande, A.: Maximizing expected utility for stochastic combinatorial optimization problems. Math. Oper. Res. 44(1), 354\u2013375 (2019)","journal-title":"Math. Oper. Res."},{"key":"1801_CR20","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Mathematical Programming The State of the Art, pp. 235\u2013257. Springer (1983)","DOI":"10.1007\/978-3-642-68874-4_10"},{"issue":"1","key":"1801_CR21","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s101070050044","volume":"85","author":"H Marchand","year":"1999","unstructured":"Marchand, H., Wolsey, L.A.: The 0\u20131 knapsack problem with a single continuous variable. Math. Program. 85(1), 15\u201333 (1999)","journal-title":"Math. Program."},{"key":"1801_CR22","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)"},{"issue":"1","key":"1801_CR23","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"6","key":"1801_CR24","doi-asserted-by":"publisher","first-page":"1666","DOI":"10.1287\/opre.1100.0866","volume":"58","author":"P Rusmevichientong","year":"2010","unstructured":"Rusmevichientong, P., Shen, Z.J.M., Shmoys, D.B.: Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Oper. Res. 58(6), 1666\u20131680 (2010)","journal-title":"Oper. Res."},{"key":"1801_CR25","unstructured":"Schoemaker, P.J.: The expected utility model: Its variants, purposes, evidence and limitations. J. Econ. Literat. pp. 529\u2013563 (1982)"},{"key":"1801_CR26","doi-asserted-by":"crossref","unstructured":"Shi, X., Prokopyev, O., Zeng, B.: Sequence independent lifting for the set of submodular maximization problem. In: International Conference on Integer Programming and Combinatorial Optimization. Springer (2020)","DOI":"10.1007\/978-3-030-45771-6_29"},{"key":"1801_CR27","unstructured":"Stobbe, P., Krause, A.: Efficient minimization of decomposable submodular functions. In: Advances in Neural Information Processing Systems, pp. 2208\u20132216 (2010)"},{"key":"1801_CR28","unstructured":"Tschiatschek, S., Iyer, R.K., Wei, H., Bilmes, J.A.: Learning mixtures of submodular functions for image collection summarization. In: Advances in Neural Information Processing Systems, pp. 1413\u20131421 (2014)"},{"key":"1801_CR29","unstructured":"Wei, K., Iyer, R., Bilmes, J.: Submodularity in data subset selection and active learning. In: International Conference on Machine Learning, pp. 1954\u20131963 (2015)"},{"issue":"1","key":"1801_CR30","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1287\/moor.2.1.66","volume":"2","author":"LA Wolsey","year":"1977","unstructured":"Wolsey, L.A.: Valid inequalities and superadditivity for 0\u20131 integer programs. Math. Oper. Res. 2(1), 66\u201377 (1977)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1801_CR31","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(89)90036-9","volume":"8","author":"LA Wolsey","year":"1989","unstructured":"Wolsey, L.A.: Submodularity and valid inequalities in capacitated fixed charge networks. Oper. Res. Lett. 8(3), 119\u2013124 (1989)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"1801_CR32","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10589-017-9958-x","volume":"69","author":"HH Wu","year":"2018","unstructured":"Wu, H.H., K\u00fc\u00e7\u00fckyavuz, S.: A two-stage stochastic programming approach for influence maximization in social networks. Comput. Optim. Appl. 69(3), 563\u2013595 (2018)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1801_CR33","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1016\/j.orl.2020.04.008","volume":"48","author":"HH Wu","year":"2020","unstructured":"Wu, H.H., K\u00fc\u00e7\u00fckyavuz, S.: An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions. Oper. Res. Lett. 48(3), 356\u2013361 (2020)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1801_CR34","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.orl.2015.12.016","volume":"44","author":"J Yu","year":"2016","unstructured":"Yu, J., Ahmed, S.: Maximizing expected utility over a knapsack constraint. Oper. Res. Lett. 44(2), 180\u2013185 (2016)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"1801_CR35","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s10107-016-1033-3","volume":"162","author":"J Yu","year":"2017","unstructured":"Yu, J., Ahmed, S.: Maximizing a class of submodular utility functions with constraints. Math. Program. 162(1\u20132), 145\u2013164 (2017)","journal-title":"Math. Program."},{"key":"1801_CR36","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.disopt.2015.07.005","volume":"24","author":"J Yu","year":"2017","unstructured":"Yu, J., Ahmed, S.: Polyhedral results for a class of cardinality constrained submodular minimization problems. Discret. Optim. 24, 87\u2013102 (2017)","journal-title":"Discret. Optim."},{"key":"1801_CR37","unstructured":"Yue, Y., Guestrin, C.: Linear submodular bandits and their application to diversified retrieval. In: Advances in Neural Information Processing Systems, pp. 2483\u20132491 (2011)"},{"key":"1801_CR38","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/978-3-540-72792-7_17","volume-title":"Integer Programming and Combinatorial Optimization","author":"B Zeng","year":"2007","unstructured":"Zeng, B., Richard, J.P.P.: A framework to derive multidimensional superadditive lifting functions and its applications. In: Fischetti, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization, pp. 210\u2013224. Springer, Heidelberg (2007)"},{"issue":"2","key":"1801_CR39","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.disopt.2010.09.004","volume":"8","author":"B Zeng","year":"2011","unstructured":"Zeng, B., Richard, J.P.P.: A polyhedral study on 0\u20131 knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting. Discret. Optim. 8(2), 259\u2013276 (2011)","journal-title":"Discret. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01801-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01801-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01801-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T03:17:09Z","timestamp":1675394229000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01801-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,22]]},"references-count":39,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1801"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01801-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,22]]},"assertion":[{"value":"1 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}