EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 50 / No 3 (July-September 2016) RAIRO-Theor. Inf. Appl., 50 3 (2016) 227-240 References
Issue
RAIRO-Theor. Inf. Appl.
Volume 50, Number 3, July-September 2016
Page(s) 227 - 240
DOI https://doi.org/10.1051/ita/2016022
Published online 10 November 2016
  1. 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’99, edited by G. Cornuéjols, R.E. Burkard and G.J. Woeginger. Vol. 1610 of Lecture Notes in Computer Science. Springer-Verlag (1999) 17–30. [Google Scholar]
  2. A. Badanidiyuru, R. Kleinberg and H. Lee, Approximating low-dimensional coverage problems. In Proc. of Symposuim on Computational Geometry, SoCG’12, Chapel Hill, NC, edited by T.K. Dey and S. Whitesides. ACM (2012) 161–170. [Google Scholar]
  3. A. Björklund, T. Husfeldt and M. Koivisto, Set partitioning via inclusion-exclusion. SIAM J. Comput. 39 (2009) 546–563. [CrossRef] [MathSciNet] [Google Scholar]
  4. M. Bläser, Computing small partial coverings. Inform. Process. Lett. 85 (2003) 327–331. [CrossRef] [MathSciNet] [Google Scholar]
  5. E. Bonnet, B. Escoffier, V.Th. Paschos and E. Tourniaire, Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization. Algorithmica 71 (2015) 566–580. [CrossRef] [MathSciNet] [Google Scholar]
  6. E. Bonnet, V.Th. Paschos and F. Sikora, Multiparameterizations for max k-set cover and related satisfiability problems. Preprint arXiv:1309.4718 (2013). [Google Scholar]
  7. L. Cai, Parameter complexity of cardinality constrained optimization problems. Comput. J. 51 (2008) 102–121. [CrossRef] [Google Scholar]
  8. L. Cai and X. Huang, Fixed-parameter approximation: conceptual framework and approximability results. In Proc. of International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 96–108. [Google Scholar]
  9. M. Cesati, The turing way to parameterized complexity. J. Comput. System Sci. 67 (2003) 654–685. [CrossRef] [MathSciNet] [Google Scholar]
  10. 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’01, edited by R. Hariharan, M. Mukund and V. Vinay. Vol. 2245 of Lect. Notes Comput. Sci. Springer-Verlag (2001) 120–131. [Google Scholar]
  11. Y. Chen, M. Grohe and M. Grüber, On parameterized approximability. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 109–120. [Google Scholar]
  12. Y. Chen and B. Lin, The constant inapproximability of the parameterized dominating set problem. Preprint arXiv:1511.00075 (2015). [Google Scholar]
  13. G. Cornuejols, M.L. Fisher and G.L. Nemhauser, Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Management Sci. 23 (1977) 789–810. [Google Scholar]
  14. F. Della Croce and V.Th. Paschos, Efficient algorithms for the max k-vertex cover problem. J. Comb. Optim. 28 (2014) 674–691. [CrossRef] [MathSciNet] [Google Scholar]
  15. 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’04, edited by R.G. Downey, M.R. Fellows and F. Dehne. Vol. 3162 of Lect. Notes Comput. Sci. Springer-Verlag (2004) 271–280. [Google Scholar]
  16. R.G. Downey and M.R. Fellows, Parameterized complexity. Monographs in Computer Science. Springer, New York (1999). [Google Scholar]
  17. R.G. Downey, M.R. Fellows and C. McCartin, Parameterized approximation problems. In Proc. of the International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 121–129. [Google Scholar]
  18. R.G. Downey, M.R. Fellows, C. McCartin and F.A. Rosamond, Parameterized approximation of dominating set problems. Inform. Process. Lett. 109 (2008) 68–70. [CrossRef] [MathSciNet] [Google Scholar]
  19. U. Feige, A threshold of lnn for approximating set cover. J. Assoc. Comput. Mach. 45 (1998) 634–652. [CrossRef] [MathSciNet] [Google Scholar]
  20. M.R. Fellows, J. Flum, D. Hermelin, M. Müller and F.A. Rosamond, W-hierarchies defined by symmetric gates. Theory Comput. Sys. 46 (2010) 311–339. [CrossRef] [MathSciNet] [Google Scholar]
  21. 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). [Google Scholar]
  22. J. Guo, R. Niedermeier and S. Wernicke, Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41 (2007) 501–520. [CrossRef] [MathSciNet] [Google Scholar]
  23. 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’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lecture Notes in Computer Science. Springer-Verlag (2006) 84–95. [Google Scholar]
  24. D. Marx, Parameterized complexity and approximation algorithms. Comput. J. 51 (2008) 60–78. [CrossRef] [Google Scholar]
  25. 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’12, 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–287. [Google Scholar]
  26. R. Niedermeier, Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006). [Google Scholar]
  27. C.H. Papadimitriou, Computational complexity. Addison-Wesley (1994). [Google Scholar]
  28. C.H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity. Prentice Hall, New Jersey (1981). [Google Scholar]
  29. 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). [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.