{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T14:08:47Z","timestamp":1774966127844,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,1,30]],"date-time":"2014-01-30T00:00:00Z","timestamp":1391040000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s10878-014-9707-3","type":"journal-article","created":{"date-parts":[[2014,1,29]],"date-time":"2014-01-29T10:57:17Z","timestamp":1390993037000},"page":"29-43","source":"Crossref","is-referenced-by-count":40,"title":["Approximation for maximizing monotone non-decreasing set functions with a greedy method"],"prefix":"10.1007","volume":"31","author":[{"given":"Zengfu","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bill","family":"Moran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuezhi","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quan","family":"Pan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,1,30]]},"reference":[{"issue":"3","key":"9707_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"A Ageev","year":"2004","unstructured":"Ageev A, Sviridenko M (2004) Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J Comb Optim 8(3):307\u2013328","journal-title":"J Comb Optim"},{"key":"9707_CR2","doi-asserted-by":"crossref","unstructured":"Alimonti P (1994) New local search approximation techniques for maximum generalized satisfiability problems. In: Proceedings of the 2nd Italian conference on algorithms and complexity, pp 40\u201353","DOI":"10.1007\/3-540-57811-0_5"},{"key":"9707_CR3","unstructured":"Badanidiyuru A, Dobzinski S, Oren S (2011) Optimization with demand oracles. In: Proceedings of the 13th ACM conference on electronic commerce, pp 110\u2013127"},{"key":"9707_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Naor J, Schwartz R (2012) A tight linear time $$(1\/2)$$ ( 1 \/ 2 ) -approximation for unconstrained submodular maximization. In: 53rd annual IEEE symposium on foundations of computer science","DOI":"10.1109\/FOCS.2012.73"},{"issue":"6","key":"9707_CR5","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu G, Chekuri C, P\u00e1l M, Vondr\u00e1k J (2011) Maximizing a submodular set function subject to a matroid constraint. SIAM J Comput 40(6):1740\u20131766","journal-title":"SIAM J Comput"},{"key":"9707_CR6","doi-asserted-by":"crossref","unstructured":"Chakrabarty D, Goel G (2008), On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP. In: Proceedings of the 49th annual IEEE symposium on foundations of computer science, pp 687\u2013696","DOI":"10.1109\/FOCS.2008.47"},{"key":"9707_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri C, Vondr\u00e1k J, Zenklusen R (2011), Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proceedings of the 43rd ACM symposium on theory of computing, pp 783\u2013792","DOI":"10.1145\/1993636.1993740"},{"issue":"3","key":"9707_CR8","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti M, Cornu\u00e9jols G (1984) Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discrete Appl Math 7(3):251\u2013274","journal-title":"Discrete Appl Math"},{"key":"9707_CR9","doi-asserted-by":"crossref","unstructured":"Dobzinski S, Schapira M (2006) An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithm, pp 1064\u20131073","DOI":"10.1145\/1109557.1109675"},{"key":"9707_CR10","doi-asserted-by":"crossref","unstructured":"Feige U (1998) A threshold of ln n for approximation set cover. J ACM 45(4):634\u2013652","DOI":"10.1145\/285055.285059"},{"key":"9707_CR11","unstructured":"Feige U, Vondr\u00e1k J (2006), Approximation algorithms for allocation problems: improveing the factor of $$1-\\frac{1}{e}$$ 1 - 1 e . In: Proceedings of 47th annual IEEE symposium on foundations of computer science, pp 667\u2013676"},{"key":"9707_CR12","doi-asserted-by":"crossref","first-page":"247","DOI":"10.4086\/toc.2010.v006a011","volume":"6","author":"U Feige","year":"1998","unstructured":"Feige U, Vondr\u00e1k J (1998) The submodular welfare problem with demand queries. Theory Comput 6:247\u2013290","journal-title":"Theory Comput"},{"key":"9707_CR13","doi-asserted-by":"crossref","unstructured":"Filmus Y, Ward J (2012) A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In: Proceedings of 53rd annual IEEE symposium on foundations of computer science","DOI":"10.1109\/FOCS.2012.55"},{"key":"9707_CR14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions - II. Math Progr Study 8:73\u201387","journal-title":"Math Progr Study"},{"key":"9707_CR15","doi-asserted-by":"crossref","unstructured":"Kempe D, Kleinberg J, Tardos E (2005) Influential nodes in a diffusion model for social networks. In: Proceedings of 32nd international colloquium on automata, languages and programming, Lisboa, Portugal","DOI":"10.1007\/11523468_91"},{"key":"9707_CR16","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0167-5060(08)70322-4","volume":"2","author":"B Korte","year":"1998","unstructured":"Korte B, Hausmann D (1998) An analysis of the greedy heuritic for independence systems. Ann Discret Math 2:65\u201374","journal-title":"Ann Discret Math"},{"key":"9707_CR17","doi-asserted-by":"crossref","unstructured":"Kulik A, Shachnai H, Tamir T (2009) Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, pp 545\u2013554","DOI":"10.1137\/1.9781611973068.60"},{"key":"9707_CR18","doi-asserted-by":"crossref","unstructured":"Lee J, Mirrokni V S, Nagarajan V, Sviridenko Maxim (2009) Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the 41st annual ACM symposium on theory of computing, pp 323\u2013332","DOI":"10.1145\/1536414.1536459"},{"issue":"4","key":"9707_CR19","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee J, Sviridenko M, Vondr\u00e1k (2010) Submodular maximization over multiple matroids via generalized exchange properties. Math Oper Res 35(4):795\u2013806","journal-title":"Math Oper Res"},{"key":"9707_CR20","unstructured":"Lloyd SP, Witsenhausen HS (1986) Weapons allocation is NP-complete. In: Proceedings of the 1986 summer conference on simulation, Reno"},{"key":"9707_CR21","unstructured":"Lu J, Suda T (2003) Coverage-aware self-scheduling in sensor networks. In: Proceedings of IEEE 18th annual workshop on computer communications, Laguna Niguel"},{"issue":"1","key":"9707_CR22","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions-I. Math Progr 14(1):265\u2013294","journal-title":"Math Progr"},{"issue":"3","key":"9707_CR23","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nembauser","year":"1978","unstructured":"Nembauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math Oper Res 3(3):177\u2013188","journal-title":"Math Oper Res"},{"issue":"1","key":"9707_CR24","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 32(1):41\u201343","journal-title":"Oper Res Lett"},{"key":"9707_CR25","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k J (2008), Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th annual ACM symposium on theory of computing, pp 67\u201374","DOI":"10.1145\/1374376.1374389"},{"key":"9707_CR26","first-page":"253","volume":"B23","author":"J Vondr\u00e1k","year":"2010","unstructured":"Vondr\u00e1k J (2010) Submodularity and curvature: the optimal algorithm. RIMS Kokyuroku Bessatsu B23:253\u2013266","journal-title":"RIMS Kokyuroku Bessatsu"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9707-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-014-9707-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-014-9707-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T18:08:12Z","timestamp":1746122892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-014-9707-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,30]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9707"],"URL":"https:\/\/doi.org\/10.1007\/s10878-014-9707-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,30]]}}}