Boolean optimization algorithm on (0,1)-matrices
type: Item
instance of: scholarly article
title: Boolean optimization algorithm on (0,1)-matrices
zbMATH Open document ID: 0778.90039
author: O. V. German
author: E. I. Germanovich
author: V. G. Najdenko
published in: Computational Mathematics and Mathematical Physics
publication date: 1993-09-06T00:00:00Z
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.
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90-08
zbMATH DE Number: 205013
zbMATH Keywords: heuristic algorithm
zbMATH Keywords: symmetric (0,1)-matrix
zbMATH Keywords: zero main diagonal
zbMATH Keywords: mathematical expectation
reviewed by: Vitali Oscarovich Groppen
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 205013