Exploiting hidden structure in selecting dimensions that distinguish vectors

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

doi:10.1016/j.jcss.2015.11.011

Exploiting hidden structure in selecting dimensions that distinguish vectors

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

Laboratory for Theoretical and Experimental Simulation of New Photonic Devices

Research output: Contribution to journal › Article

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.

Original language	English
Pages (from-to)	521-535
Number of pages	15
Journal	Journal of Computer and System Sciences
Volume	82
Issue number	3
DOIs	https://doi.org/10.1016/j.jcss.2015.11.011
Publication status	Published - 1 Jan 2016

Keywords

Combinatorial feature selection
Combinatorics of binary matrices
Dimension reduction
Fixed-parameter tractability
Machine learning
Minimal reduct problem
NP-hardness
W-hardness
Δ-Systems

Access to Document

10.1016/j.jcss.2015.11.011

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Exploiting hidden structure in selecting dimensions that distinguish vectors'. Together they form a unique fingerprint.

Cite this

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

@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",

number = "3",

}

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 -