Standard

A parameterized complexity analysis of combinatorial feature selection problems. / Froese, Vincent; Van Bevern, René; Niedermeier, Rolf et al.

Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. 2013. p. 445-456 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8087 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Froese, V, Van Bevern, R, Niedermeier, R & Sorge, M 2013, A parameterized complexity analysis of combinatorial feature selection problems. in Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8087 LNCS, pp. 445-456, 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, Klosterneuburg, Austria, 26.08.2013. https://doi.org/10.1007/978-3-642-40313-2_40

APA

Froese, V., Van Bevern, R., Niedermeier, R., & Sorge, M. (2013). A parameterized complexity analysis of combinatorial feature selection problems. In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings (pp. 445-456). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8087 LNCS). https://doi.org/10.1007/978-3-642-40313-2_40

Vancouver

Froese V, Van Bevern R, Niedermeier R, Sorge M. A parameterized complexity analysis of combinatorial feature selection problems. In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. 2013. p. 445-456. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40313-2_40

Author

Froese, Vincent ; Van Bevern, René ; Niedermeier, Rolf et al. / A parameterized complexity analysis of combinatorial feature selection problems. Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. 2013. pp. 445-456 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{633d0b79d55b476c90bb97e0d7a4ed51,
title = "A parameterized complexity analysis of combinatorial feature selection problems",
abstract = "We examine the algorithmic tractability of NP-hard combinatorial feature selection problems in terms of parameterized complexity theory. In combinatorial feature selection, one seeks to discard dimensions from high-dimensional data such that the resulting instances fulfill a desired property. In parameterized complexity analysis, one seeks to identify relevant problem-specific quantities and tries to determine their influence on the computational complexity of the considered problem. In this paper, for various combinatorial feature selection problems, we identify parameterizations and reveal to what extent these govern computational complexity. We provide tractability as well as intractability results; for example, we show that the Distinct Vectors problem on binary points is polynomial-time solvable if each pair of points differs in at most three dimensions, whereas it is NP-hard otherwise.",
author = "Vincent Froese and {Van Bevern}, Ren{\'e} and Rolf Niedermeier and Manuel Sorge",
year = "2013",
month = oct,
day = "15",
doi = "10.1007/978-3-642-40313-2_40",
language = "English",
isbn = "9783642403125",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "445--456",
booktitle = "Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings",
note = "38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 ; Conference date: 26-08-2013 Through 30-08-2013",

}

RIS

TY - GEN

T1 - A parameterized complexity analysis of combinatorial feature selection problems

AU - Froese, Vincent

AU - Van Bevern, René

AU - Niedermeier, Rolf

AU - Sorge, Manuel

PY - 2013/10/15

Y1 - 2013/10/15

N2 - We examine the algorithmic tractability of NP-hard combinatorial feature selection problems in terms of parameterized complexity theory. In combinatorial feature selection, one seeks to discard dimensions from high-dimensional data such that the resulting instances fulfill a desired property. In parameterized complexity analysis, one seeks to identify relevant problem-specific quantities and tries to determine their influence on the computational complexity of the considered problem. In this paper, for various combinatorial feature selection problems, we identify parameterizations and reveal to what extent these govern computational complexity. We provide tractability as well as intractability results; for example, we show that the Distinct Vectors problem on binary points is polynomial-time solvable if each pair of points differs in at most three dimensions, whereas it is NP-hard otherwise.

AB - We examine the algorithmic tractability of NP-hard combinatorial feature selection problems in terms of parameterized complexity theory. In combinatorial feature selection, one seeks to discard dimensions from high-dimensional data such that the resulting instances fulfill a desired property. In parameterized complexity analysis, one seeks to identify relevant problem-specific quantities and tries to determine their influence on the computational complexity of the considered problem. In this paper, for various combinatorial feature selection problems, we identify parameterizations and reveal to what extent these govern computational complexity. We provide tractability as well as intractability results; for example, we show that the Distinct Vectors problem on binary points is polynomial-time solvable if each pair of points differs in at most three dimensions, whereas it is NP-hard otherwise.

UR - http://www.scopus.com/inward/record.url?scp=84885194986&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40313-2_40

DO - 10.1007/978-3-642-40313-2_40

M3 - Conference contribution

AN - SCOPUS:84885194986

SN - 9783642403125

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 445

EP - 456

BT - Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings

T2 - 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013

Y2 - 26 August 2013 through 30 August 2013

ER -

ID: 22340869