Lagrangian Smoothing Heuristics for Max-Cut

Hernán Alperin; Ivo Nowak

edoc-Server der Humboldt-Universität zu Berlin

Band einer Schriftenreihe

Autor(en):	Hernán Alperin; Ivo Nowak
Titel:	Lagrangian Smoothing Heuristics for Max-Cut
Erscheinungsdatum:	28.05.2002
Erschienen in:	Preprints aus dem Institut für Mathematik 6 (Mathematik-Preprints) ISSN: 0863-0976
Volltext:	pdf (urn:nbn:de:kobv:11-10052535)
Fachgebiet(e):	Mathematik
Schlagwörter (eng):	semidefinite programming, quadratic programming, combinatorial optimization, non-convex programming, approximation methods and heuristics, pathfollowing, homotopy
Herausgeber:	Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link.	Endnote Bibtex
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.

Abstract (eng):

This 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.

Zugriffsstatistik:

Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.

Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.

Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.

May
11

Jun
11

Jul
11

Sep
11

Oct
11

Nov
11

Dec
11

Jan
12

Feb
12

Apr
12

May
12

Jun
12

Jul
12

Aug
12

Sep
12

Oct
12

Nov
12

Dec
12

Jan
13

Apr
13

Monat	May 11	Jun 11	Jul 11	Sep 11	Oct 11	Nov 11	Dec 11	Jan 12	Feb 12	May 12	Jun 12	Jul 12	Aug 12	Oct 12	Nov 12	Dec 12	Jan 13	Apr 13
Startseite			1		2		2	2	3	1	1			2			2	2
PDF	6	1	1	1	1	1		2			2	2	1	1	2	1	11	15

Gesamtzahl der Zugriffe seit May 2011:

Startseite – 18 (1 pro Monat)
PDF – 48 (2.4 pro Monat)

Generiert am 22.05.2013, 00:23:20