Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices

DOI10.1137/S089548010343569XzbMath1113.90101OpenAlexW2099553740MaRDI QIDQ5470794

Dion C. Gijswijt

Publication date: 1 June 2006

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s089548010343569x

zbMATH Keywords

circular arc graphcoloringcyclic schedulingtotally unimodularnearly bipartite graphinteger decomposition

Mathematics Subject Classification ID

Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (29)

On semidefinite programming bounds for graph bandwidth ⋮ Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem ⋮ Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix ⋮ Graph bisection revisited ⋮ Tight relative t-designs on two shells in hypercubes, and Hahn and Hermite polynomials ⋮ Testing additive integrality gaps ⋮ On semidefinite programming relaxations of maximum \(k\)-section ⋮ On the number of matrices to generate a matrix \(\ast\)-algebra over the real field ⋮ Semidefinite programming bounds for binary codes from a split Terwilliger algebra ⋮ A numerical algorithm for block-diagonal decomposition of matrix \(*\)-algebras with application to semidefinite programming ⋮ Coloring fuzzy circular interval graphs ⋮ The representation polyhedron of a semiorder. ⋮ Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry ⋮ The triple distribution of codes and ordered codes ⋮ High dimensional Hoffman bound and applications in extremal combinatorics ⋮ Semidefinite programming for permutation codes ⋮ One-Dimensional Quantum Cellular Automata over Finite, Unbounded Configurations ⋮ Colorings of \(k\)-balanced matrices and integer decomposition property of related polyhedra ⋮ The stable set polytope of quasi-line graphs ⋮ An axiomatic duality framework for the theta body and related convex corners ⋮ Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming ⋮ Parameterized shifted combinatorial optimization ⋮ The unimodular intersection problem ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Box-total dual integrality, box-integrality, and equimodular matrices ⋮ Polyhedra with the integer Carathéodory property ⋮ Commutative association schemes ⋮ Upper bounds for packings of spheres of several radii ⋮ Coloring Fuzzy Circular Interval Graphs

This page was built for publication: Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices