Balanced Matrices

Abstract

A 0, + or - 1 matrix A is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This definition was introduced by Truemper and generalizes the notion of balanced 0,1 matrix introduced by Berge. In this paper, we survey what is currently known about these matrices, including polyhedral results, structural theorems, recognition algorithms and the relation with some problems in logic.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1994
Accession Number
ADA280021

Entities

People

  • Ajai Kapoor
  • Gerard Corneujols
  • Kristina Vušković
  • M. R. Rao
  • Michele Conforti

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Artificial Intelligence
  • Computer Programming
  • Computer Science
  • Graph Theory
  • Inequalities
  • Integer Programming
  • Integrals
  • Linear Programming
  • Linear Systems
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Recognition
  • Theoretical Computer Science

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.