A good submatrix is hard to find

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

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

hereditary propertyidentification of submatricesidentification problemmonotone propertyNP-completenesssubmatrix

Mathematics Subject Classification ID

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

Cites work

• Converting Linear Programs to Network Problems
• Decomposition of regular matroids
• 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?)
• 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

(20)

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