Project Description
Binary quadratic optimization is the problem of minimizing (or maximizing) a real polynomial function with total degree two whose variables take value either 0 or 1. Such an nvariable function can take on as many as 2^n values, so is not straightforward to minimize. However, by adding a dummy variable one can homogenize the function in order to write it as a positive sum of parity functions of its variables, while preserving its min and max. Then the function can be viewed as a "weighted signed graph," with each vertex representing a 01 variable, and an edge representing the weighted parity relation of its endpoints.
A greedy algorithm, one that minimizes the terms in order of decreasing size, might be made reliable. Or, in order to simplify the treatment of such a function it is useful to introduce a spanning tree. So a related question is that of minimizing the degree of a spanning tree all of whose base cycles have length less than three. One of these directions will develop into a project.
