On simple combinatorial optimization problems

A.J. Hoffman

doi:10.1016/0012-365X(92)90555-T

Discrete Mathematics

Paper

01 Sep 1992

On simple combinatorial optimization problems

View publication

Abstract

We characterize (0,1) linear programming matrices for which a greedy algorithm and its dual solve certain covering and packing problems. Special cases are shortest path and minimum spanning tree algorithms. © 1992.

Paper

On the Line Graph of the Complete Tripartite Graph

A.J. Hoffman, Basharat A. Jamil

Linear and Multilinear Algebra

Paper

Bounds for the spectrum of normal matrices

E.R. Barnes, A.J. Hoffman

Linear Algebra and Its Applications

Paper

Eigenvalues and partitionings of the edges of a graph

A.J. Hoffman

Linear Algebra and Its Applications

Paper

Optimal partitions having disjoint convex and conic hulls

E.R. Barnes, A.J. Hoffman, et al.

Mathematical Programming

View all publications

Abstract

Related

On the Line Graph of the Complete Tripartite Graph

Bounds for the spectrum of normal matrices

Eigenvalues and partitionings of the edges of a graph

Optimal partitions having disjoint convex and conic hulls