Exploiting hidden structure in selecting dimensions that distinguish vectors

作者：

Highlights：

• Binary matrices solvable for small range of Hamming distances, NP-hard otherwise.

• Sunflowers as combinatorial tool for structural matrix analysis.

• FPT and W-hardness for general matrices.

摘要

•Binary matrices solvable for small range of Hamming distances, NP-hard otherwise.•Sunflowers as combinatorial tool for structural matrix analysis.•FPT and W-hardness for general matrices.

论文关键词：NP-hardness,Fixed-parameter tractability,W-hardness,Machine learning,Combinatorial feature selection,Dimension reduction,Minimal reduct problem,Combinatorics of binary matrices,Δ-Systems

论文评审过程：Received 18 July 2014, Accepted 15 November 2015, Available online 3 December 2015, Version of Record 29 December 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.11.011