Semidefinite and copositive programming have attained an
important role in combinatorial optimization in the
last two decades.
There is a strong evidence that semidefinite and
approximation models are significantly stronger than
linear ones for many combinatorial problems. In some
copositive models give even the exact value of the
The first part of the book contains beside a survey of
standard results from linear algebra and conic
programming also a new
method to solve semidefinite programs, based on the
Lagrangian method. This method named the Boundary
goes far beyond the reach of interior point methods
when the linear
constraints are nearly orthogonal.
The second part demonstrates the application of
copositive programming to the following NP-hard
combinatorial optimization: the bandwidth problem,
assignment problem, the min-cut problem and the
partitioning problem. The book also provides the
ideas how to extend the approach
to some other 0-1 problems, like the
stability number problem and the balanced vertex
Janez Povh (1973) studied mathematics at the Faculty of
mathematics and physics at University in Ljubljana. After B.Sc.
in 1998 and M.Sc. in 2002 he defended the Ph.D. thesis at the
same faculty in 2006 under supervision of dr. Franz Rendl. From
2008 he is assistant professor at the Faculty of information
studies in Novo mesto, Slovenia.