A parameterized complexity analysis of combinatorial feature selection problems

DOI10.1007/978-3-642-40313-2_40MaRDI QIDQ2849932zbMATH OpenOpenAlexFDO

Authors Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40313-2_40

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The \(k\)-feature set problem is \(W[2]\)-complete
• Multivariate complexity theory
• Reflections on multivariate algorithmics and problem parameterization
• On the complexity of some data analysis problems
• Parameterized complexity: the main ideas and connections to practical computing

Cited in

(7)

• The \(k\)-feature set problem is \(W[2]\)-complete
• scientific article; zbMATH DE number 2080452 (Why is no real title available?)
• Parameterized Complexity of Feature Selection for Categorical Data Clustering.
• Fine-grained complexity analysis of some combinatorial data science problems
• Stochastic local search for the FEATURE SET problem, with applications to microarray data
• Exploiting hidden structure in selecting dimensions that distinguish vectors
• Kernelization complexity of possible winner and coalitional manipulation problems in voting

This page was built for publication: A parameterized complexity analysis of combinatorial feature selection problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849932)