Exploiting hidden structure in selecting dimensions that distinguish vectors

DOI10.1016/J.JCSS.2015.11.011MaRDI QIDQ899584zbMATH OpenOpenAlexFDO

Authors Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge

Publication date 30 December 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.01150

zbMATH Keywords

dimension reductionmachine learningfixed-parameter tractabilityNP-hardnessW-hardness\(\Delta\)-systemscombinatorial feature selectioncombinatorics of binary matricesminimal reduct problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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 ceil(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.

Recommendations

• A double exponential lower bound for the distinct vectors problem
• A parameterized complexity analysis of combinatorial feature selection problems
• Approximability and exact resolution of the multidimensional binary vector assignment problem
• Approximability and exact resolution of the multidimensional binary vector assignment problem
• A new algorithm for finding closest pair of vectors (extended abstract)

Cites work

• scientific article; zbMATH DE number 53312 (Why is no real title available?)
• scientific article; zbMATH DE number 108581 (Why is no real title available?)
• scientific article; zbMATH DE number 3598539 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3414305 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• 10.1162/153244303322753616
• 10.1162/153244303322753670
• A parameterized complexity analysis of combinatorial feature selection problems
• Digraphs
• Extremal combinatorics. With applications in computer science
• Fundamentals of parameterized complexity
• Kernelization lower bounds through colors and IDs
• On distance-3 matchings and induced matchings
• On explaining integer vectors by few homogeneous segments
• Parameterized algorithms
• Parameterized complexity of finding regular induced subgraphs
• Parametrized complexity theory.
• Selection of relevant features and examples in machine learning
• Structure preserving reductions among convex optimization problems
• The \(k\)-feature set problem is \(W[2]\)-complete
• Tight lower bounds for certain parameterized NP-hard problems
• Towards optimal and expressive kernelization for \(d\)-hitting set

Cited in

(6)

• The complexity of dependency detection and discovery in relational databases
• scientific article; zbMATH DE number 7651160 (Why is no real title available?)
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
• The complexity of binary matrix completion under diameter constraints
• A double exponential lower bound for the distinct vectors problem

This page was built for publication: Exploiting hidden structure in selecting dimensions that distinguish vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899584)