{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:05:47Z","timestamp":1749873947049,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662541098"},{"type":"electronic","value":"9783662541104"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-54110-4_23","type":"book-chapter","created":{"date-parts":[[2016,12,10]],"date-time":"2016-12-10T13:48:58Z","timestamp":1481377738000},"page":"324-338","source":"Crossref","is-referenced-by-count":2,"title":["FPT Approximation Schemes for Maximizing Submodular Functions"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Skowron","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,11]]},"reference":[{"key":"23_CR1","unstructured":"Bach, F.: Structured sparsity-inducing norms through submodular functions. In: Proceedings of Advances in Neural Information Processing Systems 23 (NIPS 2010), pp. 118\u2013126 (2010)"},{"key":"23_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 182\u2013196. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-72792-7_15"},{"issue":"3","key":"23_CR3","doi-asserted-by":"crossref","first-page":"718","DOI":"10.2307\/1957270","volume":"77","author":"B Chamberlin","year":"1983","unstructured":"Chamberlin, B., Courant, P.: Representative deliberations and representative decisions: proportional representation and the borda rule. Am. Polit. Sci. Rev. 77(3), 718\u2013733 (1983)","journal-title":"Am. Polit. Sci. Rev."},{"issue":"3","key":"23_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"23_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015)"},{"key":"23_CR6","unstructured":"Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Getoor, L., Scheffer, T. (eds.) Proceedings of the 28th International Conference on Machine Learning (ICML 2011), New York, NY, USA, pp. 1057\u20131064 (2011)"},{"key":"23_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)"},{"issue":"4","key":"23_CR8","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"23_CR9","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"23_CR10","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"4","key":"23_CR11","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Jegelka, S., Bilmes, J.A.: Submodularity beyond submodular energies: coupling edges in graph cuts. In: Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2011), pp. 1897\u20131904 (2011)","DOI":"10.1109\/CVPR.2011.5995589"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Kim, G., Xing, E.P., Fei-Fei, L., Kanade, T.: Distributed cosegmentation via submodular optimization on anisotropic diffusion. In: Proceedings of IEEE International Conference on Computer Vision (ICCV 2011), pp. 169\u2013176 (2011)","DOI":"10.1109\/ICCV.2011.6126239"},{"key":"23_CR14","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. Technical report (2012)"},{"key":"23_CR15","unstructured":"Krause, A., Guestrin, C.: Near-optimal value of information in graphical models. In: Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI 2005), July 2005"},{"key":"23_CR16","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235\u2013284 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in MapReduce and streaming. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013), pp. 1\u201310 (2013)","DOI":"10.1145\/2486159.2486168"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 323\u2013332 (2009)","DOI":"10.1145\/1536414.1536459"},{"key":"23_CR19","unstructured":"Lin, H., Bilmes, J.: Multi-document summarization via budgeted maximization of submodular functions. In: Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (HTL 2010), pp. 912\u2013920. Association for Computational Linguistics, Stroudsburg (2010)"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Lin, H., Bilmes, J.A.: How to select a good training-data subset for transcription: submodular active selection for sequences. In: Proceedings of 10th Annual Conference of the International Speech Communication Association (INTERSPEECH 2009), pp. 2859\u20132862 (2009)","DOI":"10.21437\/Interspeech.2009-730"},{"key":"23_CR21","unstructured":"Lu, T., Boutilier, C.: Budgeted social choice: from consensus to personalized decision making. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), pp. 280\u2013286 (2011)"},{"key":"23_CR22","unstructured":"Narasimhan, M., Nebojsa, J., Jeff, B.A.: Q-clustering. In: Weiss, Y., Sch\u00f6lkopf, B., Platt, J. (eds.) Proceedings of Advances in Neural Information Processing Systems 18 (NIPS 2010), pp. 979\u2013986. MIT Press (2006)"},{"issue":"1","key":"23_CR23","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G Nemhauser","year":"1978","unstructured":"Nemhauser, G., Wolsey, L., Fisher, M.: An analysis of approximations for maximizing submodular set functions. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"23_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"23_CR25","unstructured":"Jegelka, S., Bach, F., Sra, S.: Reflection methods for user-friendly submodular optimization. In: Burges, C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K. (eds.) Proceedings of Advances in Neural Information Processing Systems 26 (NIPS 2013), pp. 1313\u20131321. Curran Associates Inc. (2013)"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"Skowron, P.: FPT approximation schemes for maximizing submodular functions. Technical report arXiv:1510.00215 [cs.DS], January 2015","DOI":"10.1007\/978-3-662-54110-4_23"},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"Skowron, P., Faliszewski, P.: Fully proportional representation with approval ballots: approximating the maxcover problem with bounded frequencies in FPT time. In: Proceedings of the 29th Conference on Artificial Intelligence (AAAI 2015), pp. 2124\u20132130 (2015)","DOI":"10.1609\/aaai.v29i1.9432"},{"key":"23_CR28","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.artint.2016.09.003","volume":"241","author":"P Skowron","year":"2016","unstructured":"Skowron, P., Faliszewski, P., Lang, J.: Finding a collective set of items: from proportional multirepresentation to group recommendation. Artif. Intell. 241, 191\u2013216 (2016)","journal-title":"Artif. Intell."},{"key":"23_CR29","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.artint.2015.01.003","volume":"222","author":"P Skowron","year":"2015","unstructured":"Skowron, P., Faliszewski, P., Slinko, A.: Achieving fully proportional representation: approximability result. Artif. Intell. 222, 67\u2013103 (2015)","journal-title":"Artif. Intell."},{"key":"23_CR30","unstructured":"Streeter, M.J., Golovin, D.: An online algorithm for maximizing submodular functions. In: Proceedings of Advances in Neural Information Processing Systems 21 (NIPS 2008), pp. 1577\u20131584 (2008)"},{"issue":"1","key":"23_CR31","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.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"23_CR32","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"},{"key":"23_CR33","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011), pp. 783\u2013792 (2011)","DOI":"10.1145\/1993636.1993740"},{"key":"23_CR34","unstructured":"Yue, Y., Guestrin, C.: Linear submodular bandits and their application to diversified retrieval. In: Proceedings of Advances in Neural Information Processing Systems 24 (NIPS 2011), pp. 2483\u20132491 (2011)"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-54110-4_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T12:45:37Z","timestamp":1749818737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-54110-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662541098","9783662541104"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-54110-4_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}