From graph orientation to the unweighted maximum cutReportar como inadecuado




From graph orientation to the unweighted maximum cut - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 METHODES-SAMOVAR - Méthodes et modèles pour les réseaux SAMOVAR - Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux 2 RS2M - Département Réseaux et Services Multimédia Mobiles 3 SAMOVAR - Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux

Abstract : In this paper, starting from graph orientation problems, we introduce some new mixed integer linear programming formulations for the unweighted maximum cut problem. Then a new semidefinite relaxation is proposed and shown to be tighter than the Goemans and Williamson-s semidefinite relaxation. Preliminary computational results are also reported

Keywords : Graph theory Maximum cut Graph orientation Complexity NP-complete Approximation algorithm Mixed Integer Programming Semidefinite Programming





Autor: Walid Ben-Ameur - Antoine Glorieux - José Neto -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados