ISSN:
1436-5057
Keywords:
90C06
;
90C27
;
Max-cut problem
;
semidefinite programming
;
min-max eigenvalue problem
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Es wird eine obere Schranke für das Max-Cut Problem untersucht, die sich aus einer Relaxation des diskreten Problems zu einem stetigen, nichtlinearen konvexen Problem ergibt. Die Relaxation ist polynomial lösbar. Es werden die Grenzen des Ansatzes unter dem Einsatz fortgeschrittener Methoden aus numerischer linearer Algebra und nichtglatter Optimierung untersucht. Verschiedene Graphenklassen mit bis zu 50 000 Knoten und 4 Millionen Kanten werden mit dem Ansatz behandelt. Da die theoretische obere Schranke in der Praxis nur mit einer gewissen Genauigkeit bestimmt werden kann, wird ein Dualitätsmodell zwischen knoten- und kantenorientierten Relaxationen verwendet, um den Unterschied zwischen der theoretischen und der berechneten Schranke abzuschätzen.
Notes:
Abstract We study an upper bound on the max-cut problem defined via a relaxation of the discrete problem to a continuous nonlinear convex problem, which can be solved efficiently. We demonstrate how far the approach can be pushed using advanced techniques from numerical linear algebra and nonsmooth optimization. Various classes of graphs with up to 50 000 nodes and up to four million edges are considered. Since the theoretical bound can be computed only with a certain precision in practice, we use duality between node- and edge-oriented relaxations to estimate the difference between the theoretical and the computed bounds.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02238072
Permalink
