Recognizing balanceable matrices

A 0/±1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed ±1 so that the resulting matrix is balanced. A signing algorithm...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2006-02, Vol.105 (2-3), p.161-179
Main Authors: CONFORTI, Michele, ZAMBELLI, Giacomo
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
Graphs
Integer programming
Mathematical models
Mathematical programming
Operational research and scientific management
Operational research. Management science
Studies
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A 0/±1 matrix is balanced if it does not contain a square submatrix with exactly two nonzero entries per row and per column in which the sum of all entries is 2 modulo 4. A 0/1 matrix is balanceable if its nonzero entries can be signed ±1 so that the resulting matrix is balanced. A signing algorithm due to Camion shows that the problems of recognizing balanced 0/±1 matrices and balanceable 0/1 matrices are equivalent. Conforti, Cornuejols, Kapoor and Vuskovic gave an algorithm to test if a 0/±1 matrix is balanced. Truemper has characterized balanceable 0/1 matrices in terms of forbidden submatrices. In this paper we give an algorithm that explicitly finds one of these forbidden submatrices or shows that none exists. [PUBLICATION ABSTRACT]
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-005-0647-7