A good submatrix is hard to find

DOI10.1016/0167-6377(82)90038-4MaRDI QIDQ1836717zbMATHOpenAlexFDO

Authors 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

NP-completenesshereditary propertyidentification problemmonotone propertysubmatrixidentification of submatrices

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3724611 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3212891 (Why is no real title available?)
• Converting Linear Programs to Network Problems
• Decomposition of regular matroids
• Incidence matrices and interval graphs
• Matrix characterizations of circular-arc graphs
• Node-Deletion Problems on Bipartite Graphs
• On the complexity of the maximum subgraph problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(18)

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

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

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