Boolean optimization algorithm on (0,1)-matrices

MaRDI QIDQ1802588zbMATH OpenFDO

Authors O. V. German, E. I. Germanovich, V. G. Najdenko

Publication date 6 September 1993

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

zbMATH Keywords

heuristic algorithmmathematical expectationsymmetric (0,1)-matrixzero main diagonal

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Boolean programming (90C09)

Review text

Proposed is a heuristic algorithm for the solution of some class of NP- complete problems with Boolean variables. The solution of problems of this class can be presented as search of a maximal zero submatrix in a given symmetric (0,1)-matrix with zero main diagonal. The general idea of this algorithm is connected with stepping in the best direction, the last being determined as mathematical expectation of a number of maximal zero submatrices. In some cases this approach is 10 times faster than the famous regular algorithms, such as branch and bound methods.

Recommendations

• A heuristic for Boolean optimization problems
• Publication:3204332
• scientific article; zbMATH DE number 3862927
• scientific article; zbMATH DE number 3314879
• scientific article; zbMATH DE number 4083547

Cited in

(7)

• A heuristic for Boolean optimization problems
• \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems
• Eliminating switching components in binary matrices by 0-1 flips and column permutations
• scientific article; zbMATH DE number 4181142 (Why is no real title available?)
• Boolean Methods of Optimization over Independence Systems
• Determinant Optimization on Binary Matrices
• scientific article; zbMATH DE number 8033 (Why is no real title available?)

This page was built for publication: Boolean optimization algorithm on (0,1)-matrices

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