{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:20Z","timestamp":1747173440442,"version":"3.40.5"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2021,11,16]],"date-time":"2021-11-16T00:00:00Z","timestamp":1637020800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a two-stage submodular maximization problem subject to a cardinality constraint and <jats:italic>k<\/jats:italic> matroid constraints, where the objective function is the expected difference of a nonnegative monotone submodular function and a nonnegative monotone modular function. We give two bi-factor approximation algorithms for this problem. The first is a deterministic <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129521000372_inline1.png\"\/><jats:tex-math>$\\left( {{1 \\over {k + 1}}\\left( {1 - {1 \\over {{e^{k + 1}}}}} \\right),1} \\right)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm, and the second is a randomized <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129521000372_inline2.png\"\/><jats:tex-math>$\\left( {{1 \\over {k + 1}}\\left( {1 - {1 \\over {{e^{k + 1}}}}} \\right) - \\varepsilon ,1} \\right)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-approximation algorithm with improved time efficiency.<\/jats:p>","DOI":"10.1017\/s0960129521000372","type":"journal-article","created":{"date-parts":[[2021,11,16]],"date-time":"2021-11-16T01:50:54Z","timestamp":1637027454000},"page":"211-226","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Two-stage submodular maximization problem beyond nonnegative and monotone"],"prefix":"10.1017","volume":"34","author":[{"given":"Zhicheng","family":"Liu","sequence":"first","affiliation":[]},{"given":"Hong","family":"Chang","sequence":"additional","affiliation":[]},{"given":"Ran","family":"Ma","sequence":"additional","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2224-1484","authenticated-orcid":false,"given":"Xiaoyan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2021,11,16]]},"reference":[{"doi-asserted-by":"publisher","key":"S0960129521000372_ref17","DOI":"10.1007\/BF01588971"},{"unstructured":"Stan, S. , Zadimoghaddam, M. , Krause, A. and Karbasi, A. (2017). Probabilistic submodular maximization in sub-linear time. In: ICML, 3241\u20133250.","key":"S0960129521000372_ref19"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref4","DOI":"10.1137\/080733991"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref13","DOI":"10.1137\/090750020"},{"volume-title":"Combinatorial Optimization-Polyhedra and Efficiency","year":"2003","key":"S0960129521000372_ref18"},{"unstructured":"Ward, J. (2012). Oblivious and Non-Oblivious Local Search for Combinatorial Optimization. Phd thesis, University of Toronto.","key":"S0960129521000372_ref21"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref9","DOI":"10.1137\/130920277"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref14","DOI":"10.1007\/978-3-030-59267-7_13"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref3","DOI":"10.1137\/130929205"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref6","DOI":"10.1109\/FOCS.2016.34"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref8","DOI":"10.1109\/FOCS.2011.46"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref10","DOI":"10.1137\/1.9781611973082.83"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref1","DOI":"10.1007\/978-3-642-23719-5_28"},{"doi-asserted-by":"crossref","unstructured":"Mirzasoleiman, B. , Badanidiyuru, A. , Karbasi, A. , Vondra\u00e1k, J. and Krause, A. (2015). Lazier than lazy greedy. In: AAAI, 1812\u20131818.","key":"S0960129521000372_ref15","DOI":"10.1609\/aaai.v29i1.9486"},{"unstructured":"Balkanski, E. , Mirzasoleiman, B. , Krause, A. and Singer, Y. (2016). Learning sparse combinatorial representations via two-stage submodular maximization. In: ICML, 2207\u20132216.","key":"S0960129521000372_ref2"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref20","DOI":"10.1287\/moor.2016.0842"},{"unstructured":"Mitrovic, M. , Kazemi, E. , Zadimoghaddam, M. and Karbasi, A. (2018). Data summarization at scale: A two-stage submodular approach. In: ICML, 3593\u20133602.","key":"S0960129521000372_ref16"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref5","DOI":"10.1145\/1109557.1109675"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref7","DOI":"10.1007\/978-3-030-24766-9_28"},{"doi-asserted-by":"publisher","key":"S0960129521000372_ref12","DOI":"10.1287\/moor.2013.0592"},{"unstructured":"Harshaw, C. , Feldman, M. , Ward, J. and Karbasi, A. (2019). Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In: ICML, 2634\u20132643.","key":"S0960129521000372_ref11"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129521000372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T11:02:00Z","timestamp":1717412520000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129521000372\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,16]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S0960129521000372"],"URL":"https:\/\/doi.org\/10.1017\/s0960129521000372","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2021,11,16]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}