{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T09:25:36Z","timestamp":1770888336800,"version":"3.50.1"},"reference-count":29,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1051\/ita\/2016022","type":"journal-article","created":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T07:33:47Z","timestamp":1478763227000},"page":"227-240","source":"Crossref","is-referenced-by-count":14,"title":["Parameterized exact and approximation algorithms for maximum<i>k<\/i>-set cover and related satisfiability problems"],"prefix":"10.1051","volume":"50","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2016,11,10]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"A.A. Ageev and M. Sviridenko, Approximation algorithms for maximum coverage and max cut with given sizes of parts. In Proc. of Conference on Integer Programming and Combinatorial Optimization, IPCO\u201999, edited by G. Cornu\u00e9jols, R.E. Burkard and G.J. Woeginger. Vol. 1610 of Lecture Notes in Computer Science. Springer-Verlag (1999) 17\u201330.","DOI":"10.1007\/3-540-48777-8_2"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. Badanidiyuru, R. Kleinberg and H. Lee, Approximating low-dimensional coverage problems. In Proc. of Symposuim on Computational Geometry, SoCG\u201912, Chapel Hill, NC, edited by T.K. Dey and S. Whitesides. ACM (2012) 161\u2013170.","DOI":"10.1145\/2261250.2261274"},{"key":"R3","first-page":"546","volume":"39","author":"Bj\u00f6rklund","year":"2009"},{"key":"R4","first-page":"327","volume":"85","author":"Bl\u00e4ser","year":"2003"},{"key":"R5","first-page":"566","volume":"71","author":"Bonnet","year":"2015"},{"key":"R6","unstructured":"E. Bonnet, V.Th. Paschos and F. Sikora, Multiparameterizations for max k-set cover and related satisfiability problems. Preprint arXiv:1309.4718 (2013)."},{"key":"R7","first-page":"102","volume":"51","author":"Cai","year":"2008"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"L. Cai and X. Huang, Fixed-parameter approximation: conceptual framework and approximability results. In Proc. of International Workshop on Parameterized and Exact Computation, IWPEC\u201906, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 96\u2013108.","DOI":"10.1007\/11847250_9"},{"key":"R9","first-page":"654","volume":"67","author":"Cesati","year":"2003"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"J. Chen, D.K. Friesen, W. Jia and I.A. Kanj, Using nondeterminism to design deterministic algorithms. In Proc. of Foundations of Software Technology and Theoretical Computer Science, FSTTCS\u201901, edited by R. Hariharan, M. Mukund and V. Vinay. Vol. 2245 of Lect. Notes Comput. Sci. Springer-Verlag (2001) 120\u2013131.","DOI":"10.1007\/3-540-45294-X_11"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Y. Chen, M. Grohe and M. Gr\u00fcber, On parameterized approximability. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC\u201906, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 109\u2013120.","DOI":"10.1007\/11847250_10"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Y. Chen and B. Lin, The constant inapproximability of the parameterized dominating set problem. Preprint arXiv:1511.00075 (2015).","DOI":"10.1109\/FOCS.2016.61"},{"key":"R13","first-page":"789","volume":"23","author":"Cornuejols","year":"1977"},{"key":"R14","first-page":"674","volume":"28","author":"Della Croce","year":"2014"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"F. Dehne, M.R. Fellows, F.A. Rosamond and P. Shaw, Greedy localization, iterative compression, modeled crown reductions: new FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC\u201904, edited by R.G. Downey, M.R. Fellows and F. Dehne. Vol. 3162 of Lect. Notes Comput. Sci. Springer-Verlag (2004) 271\u2013280.","DOI":"10.1007\/978-3-540-28639-4_24"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"R.G. Downey and M.R. Fellows, Parameterized complexity. Monographs in Computer Science. Springer, New York (1999).","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R.G. Downey, M.R. Fellows and C. McCartin, Parameterized approximation problems. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC\u201906, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 121\u2013129.","DOI":"10.1007\/11847250_11"},{"key":"R18","first-page":"68","volume":"109","author":"Downey","year":"2008"},{"key":"R19","first-page":"634","volume":"45","author":"Feige","year":"1998"},{"key":"R20","first-page":"311","volume":"46","author":"Fellows","year":"2010"},{"key":"R21","unstructured":"M.R. Garey and D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, edited by W. H. Freeman, San Francisco (1979)."},{"key":"R22","first-page":"501","volume":"41","author":"Guo","year":"2007"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Y. Liu, S. Lu, J. Chen and S.-H. Sze, Greedy localization and color-coding: improved matching and packing algorithms. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC\u201906, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lecture Notes in Computer Science. Springer-Verlag (2006) 84\u201395.","DOI":"10.1007\/11847250_8"},{"key":"R24","first-page":"60","volume":"51","author":"Marx","year":"2008"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"D. Moshkovitz, The projection games conjecture and the NP-hardness of lnn-approximating set-cover. In Proc. of Workshop on Approximation Algorithms for Combinatorial Optimization Problems and Workshop on Randomization and Computation, APPROX-RANDOM\u201912, edited by A. Gupta, K. Jansen, J.D.P. Rolim and R.A. Servedio. Vol. 7408 of Lecture Notes in Computer Science. Springer-Verlag (2012) 276\u2013287.","DOI":"10.1007\/978-3-642-32512-0_24"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"R. Niedermeier, Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006).","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"R27","unstructured":"C.H. Papadimitriou, Computational complexity. Addison-Wesley (1994)."},{"key":"R28","unstructured":"C.H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity. Prentice Hall, New Jersey (1981)."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"P. Skowron and P. Faliszewski, In Fully proportional representation with approval ballots: approximating the maxcover problem with bounded frequencies in FPT time. AAAI Conference on Artificial Intelligence (2015).","DOI":"10.1609\/aaai.v29i1.9432"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2016022\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T00:34:35Z","timestamp":1657672475000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2016022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7]]},"references-count":29,"journal-issue":{"issue":"3"},"alternative-id":["ita160005"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2016022","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7]]}}}