A parameterized complexity analysis of combinatorial feature selection problems

Vincent Froese, René Van Bevern, Rolf Niedermeier, Manuel Sorge

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

4 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииMathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings
Страницы445-456
Число страниц12
DOI
СостояниеОпубликовано - 15 окт 2013
Опубликовано для внешнего пользованияДа
Событие38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Австрия
Продолжительность: 26 авг 201330 авг 2013

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том8087 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
СтранаАвстрия
ГородKlosterneuburg
Период26.08.201330.08.2013

Fingerprint Подробные сведения о темах исследования «A parameterized complexity analysis of combinatorial feature selection problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

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