A good submatrix is hard to find

DOI10.1016/0167-6377(82)90038-4zbMath0506.15012OpenAlexW2002630401MaRDI QIDQ1836717

John J. III Bartholdi

Publication date: 1982

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(82)90038-4

zbMATH Keywords

identification problemNP-completenesshereditary propertymonotone propertysubmatrixidentification of submatrices

Mathematics Subject Classification ID

Hermitian, skew-Hermitian, and related matrices (15B57) Mathematical programming (90C99)

Related Items (17)

Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format ⋮ Optimal Transitions for Targeted Protein Quantification: Best Conditioned Submatrix Selection ⋮ A network relaxation based enumeration algorithm for set partitioning ⋮ Rectangular maximum-volume submatrices and their applications ⋮ A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph ⋮ Linear optimization over homogeneous matrix cones ⋮ Use of hidden network structure in the set partitioning problem ⋮ Parallel cross interpolation for high-precision calculation of high-dimensional integrals ⋮ Extracting pure network submatrices in linear programs using signed graphs. ⋮ Quasioptimality of maximum-volume cross interpolation of tensors ⋮ Generalizing the column-row matrix decomposition to multi-way arrays ⋮ An exact approach to the problem of extracting an embedded network matrix ⋮ The practical conversion of linear programmes to network flow models ⋮ Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs ⋮ Robust CUR Decomposition: Theory and Imaging Applications ⋮ Extracting embedded generalized networks from linear programming problems ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• Decomposition of regular matroids
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• Matrix characterizations of circular-arc graphs
• Converting Linear Programs to Network Problems
• Node-Deletion Problems on Bipartite Graphs
• On the complexity of the Maximum Subgraph Problem

This page was built for publication: A good submatrix is hard to find