A Cut Approach to a Class of Quadratic Integer Programming Problems.

摘要

This paper presents an efficient algorithm for solving a class of quadratic integer programming problems. These problems include discrete versions of the quadratic placement problem and the squared Euclidean distance problem. The algorithm solves a finite sequence of minimum cut problems, or equivalently maximum flow problems, on a graph with n + 2 vertices where n is the number of variables in the problem. (Author)