Standard

Exploiting hidden structure in selecting dimensions that distinguish vectors. / Froese, Vincent; Van Bevern, René; Niedermeier, Rolf et al.

In: Journal of Computer and System Sciences, Vol. 82, No. 3, 01.01.2016, p. 521-535.

Research output: Contribution to journal › Article › peer-review

Harvard

Froese, V, Van Bevern, R, Niedermeier, R & Sorge, M 2016, 'Exploiting hidden structure in selecting dimensions that distinguish vectors', Journal of Computer and System Sciences, vol. 82, no. 3, pp. 521-535. https://doi.org/10.1016/j.jcss.2015.11.011

APA

Froese, V., Van Bevern, R., Niedermeier, R., & Sorge, M. (2016). Exploiting hidden structure in selecting dimensions that distinguish vectors. Journal of Computer and System Sciences, 82(3), 521-535. https://doi.org/10.1016/j.jcss.2015.11.011

Vancouver

Froese V, Van Bevern R, Niedermeier R, Sorge M. Exploiting hidden structure in selecting dimensions that distinguish vectors. Journal of Computer and System Sciences. 2016 Jan 1;82(3):521-535. doi: 10.1016/j.jcss.2015.11.011

Author

Froese, Vincent ; Van Bevern, René ; Niedermeier, Rolf et al. / Exploiting hidden structure in selecting dimensions that distinguish vectors. In: Journal of Computer and System Sciences. 2016 ; Vol. 82, No. 3. pp. 521-535.

BibTeX

@article{ca891bd5b4d440aab0fede56b31ccdc4,
title = "Exploiting hidden structure in selecting dimensions that distinguish vectors",
abstract = "The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main result is that, for binary matrices, there is a complexity dichotomy for Distinct Vectors based on the maximum (H) and the minimum (h) pairwise Hamming distance between matrix rows: Distinct Vectors can be solved in polynomial time if H≤2[h/2]+1, and is NP-complete otherwise. Moreover, we explore connections of Distinct Vectors to hitting sets, thereby providing several fixed-parameter tractability and intractability results also for general matrices.",
keywords = "Combinatorial feature selection, Combinatorics of binary matrices, Dimension reduction, Fixed-parameter tractability, Machine learning, Minimal reduct problem, NP-hardness, W-hardness, Δ-Systems",
author = "Vincent Froese and {Van Bevern}, Ren{\'e} and Rolf Niedermeier and Manuel Sorge",
year = "2016",
month = jan,
day = "1",
doi = "10.1016/j.jcss.2015.11.011",
language = "English",
volume = "82",
pages = "521--535",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "3",

}

RIS

TY - JOUR

T1 - Exploiting hidden structure in selecting dimensions that distinguish vectors

AU - Froese, Vincent

AU - Van Bevern, René

AU - Niedermeier, Rolf

AU - Sorge, Manuel

PY - 2016/1/1

Y1 - 2016/1/1

N2 - The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main result is that, for binary matrices, there is a complexity dichotomy for Distinct Vectors based on the maximum (H) and the minimum (h) pairwise Hamming distance between matrix rows: Distinct Vectors can be solved in polynomial time if H≤2[h/2]+1, and is NP-complete otherwise. Moreover, we explore connections of Distinct Vectors to hitting sets, thereby providing several fixed-parameter tractability and intractability results also for general matrices.

AB - The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main result is that, for binary matrices, there is a complexity dichotomy for Distinct Vectors based on the maximum (H) and the minimum (h) pairwise Hamming distance between matrix rows: Distinct Vectors can be solved in polynomial time if H≤2[h/2]+1, and is NP-complete otherwise. Moreover, we explore connections of Distinct Vectors to hitting sets, thereby providing several fixed-parameter tractability and intractability results also for general matrices.

KW - Combinatorial feature selection

KW - Combinatorics of binary matrices

KW - Dimension reduction

KW - Fixed-parameter tractability

KW - Machine learning

KW - Minimal reduct problem

KW - NP-hardness

KW - W-hardness

KW - Δ-Systems

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

U2 - 10.1016/j.jcss.2015.11.011

DO - 10.1016/j.jcss.2015.11.011

M3 - Article

AN - SCOPUS:84949024355

VL - 82

SP - 521

EP - 535

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 3

ER -

ID: 22339710