DIMACS TR: 93-18
Convex Relaxations of 0-1 Quadratic Programming
Authors: Svatopluk Poljak and Henry Wolkowicz
ABSTRACT
We consider three parametric relaxations of the
0-1 quadratic programming problem. These relaxations are to:
quadratic maximization over simple box constraints,
quadratic maximization over the sphere, and
the maximum eigenvalue of a bordered matrix.
When minimized over the parameter, each of the relaxations
provides an upper bound on the original discrete
problem. Moreover, these bounds
are efficiently computable.
Our main result is that, surprisingly, all three bounds
are equal.
Henry Wolkowicz; Department of Combinatorics and Optimization;
Faculty of Math.; Univ. of Waterloo; Waterloo, Ont., Canada N2L 3G1
(on sabbatical leave at Princeton University, Dept. of Civil Engineering
and Operations Research, Princeton, NJ 08544, 609-258-3839)
{hwolkowicz@orion.uwaterloo.ca; na.wolkowicz@na-net.ornl.gov}
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-18.ps
DIMACS Home Page