Show simple item record

2002-05-28Buch DOI: 10.18452/2619
Lagrangian Smoothing Heuristics for Max-Cut
dc.contributor.authorAlperin, Hernán
dc.contributor.authorNowak, Ivo
dc.date.accessioned2017-06-15T17:44:50Z
dc.date.available2017-06-15T17:44:50Z
dc.date.created2005-11-04
dc.date.issued2002-05-28
dc.identifier.issn0863-0976
dc.identifier.urihttp://edoc.hu-berlin.de/18452/3271
dc.description.abstractThis paper presents smoothing heuristics for an NP-hard combinatorial problem based on Lagrangian relaxation. We formulate the Lagrangian dual for this nonconvex quadratic problem and propose eigenvalue nonsmooth unconstrained optimization to solve the dual problem with bundle or subgradient methods. Derived heuristics are considered to obtain good primal solutions through pathfollowing methods using a projected gradient algorithm. Starting points are drawn using several sampling techniques that use randomization and eigenvectors. The proposed method turns out to be competitive with the most recent ones. The idea presented here is generic and can be generalized, to all problems where convex Lagrangian relaxation can be applied. Furthermore, to the best of our knowledge, this is the first time that a Lagrangian heuristic is combined with pathfollowing techniques.eng
dc.language.isoeng
dc.publisherHumboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik
dc.subjectsemidefinite programmingeng
dc.subjectquadratic programmingeng
dc.subjectcombinatorial optimizationeng
dc.subjectnon-convex programmingeng
dc.subjectapproximation methods and heuristicseng
dc.subjectpathfollowingeng
dc.subjecthomotopyeng
dc.subject.ddc510 Mathematik
dc.titleLagrangian Smoothing Heuristics for Max-Cut
dc.typebook
dc.identifier.urnurn:nbn:de:kobv:11-10052535
dc.identifier.doihttp://dx.doi.org/10.18452/2619
local.edoc.container-titlePreprints aus dem Institut für Mathematik
local.edoc.pages24
local.edoc.type-nameBuch
local.edoc.container-typeseries
local.edoc.container-type-nameSchriftenreihe
local.edoc.container-volume2002
local.edoc.container-issue6
local.edoc.container-year2002
local.edoc.container-erstkatid2075199-0

Show simple item record