Graph-theoretic representations for proximity matrices through strongly-anti-Robinson or circular strongly-anti-Robinson matrices

There are various optimization strategies for approximating, through the minimization of a least-squares loss function, a given symmetric proximity matrix by a sum of matrices each subject to some collection of order constraints on its entries. We extend these approaches to include components in the approximating sum that satisfy what are called the strongly-anti-Robinson (SAR) or circular strongly-anti-Robinson (CSAR) restrictions. A matrix that is SAR or CSAR is representable by a particular graph-theoretic structure, where each matrix entry is reproducible from certain minimum path lengths in the graph. One published proximity matrix is used extensively to illustrate the types of approximation that ensue when the SAR or CSAR constraints are imposed.The authors are indebted to Boris Mirkin who first noted in a personal communication to one of us (LH, April 22, 1996) that the optimization method for fitting anti-Robinson matrices in Hubert and Arabie (1994) should be extendable to the fitting of strongly anti-Robinson matrices as well.