Student: Alex Waldron
School: Harvard College, Math
Research Area(s): Operations Research, Graph Theory
Project Name: Weighted Signed Graphs in Quadratic Binary Optimization
Faculty Advisor: Dr. Endre Boros , RUTCOR, Rutgers University Center for Operations Research

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 n-variable 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 0-1 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.