Towards the optimum by semidefinite and copositive programming : New approach to approximate hard optimization problems

ISBN-13: 9783639166545 / Angielski / Miękka / 2009 / 132 str.

Janez Povh

Opis

Semidefinite and copositive programming have attained animportant role in combinatorial optimization in thelast two decades.There is a strong evidence that semidefinite andcopositiveapproximation models are significantly stronger thanthe purelylinear ones for many combinatorial problems. In somecases thecopositive models give even the exact value of theproblem.The first part of the book contains beside a survey ofstandard results from linear algebra and conicprogramming also a newmethod to solve semidefinite programs, based on theaugmentedLagrangian method. This method named the Boundarypoint methodgoes far beyond the reach of interior point methodswhen the linearconstraints are nearly orthogonal.The second part demonstrates the application ofsemidefinite andcopositive programming to the following NP-hardproblems fromcombinatorial optimization: the bandwidth problem,the quadraticassignment problem, the min-cut problem and thegeneral graphpartitioning problem. The book also provides theideas how to extend the approachto some other 0-1 problems, like the stability number problem and the balanced vertexseparator problem.

O autorze

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.