Publication

Asymptotics for geometric combinatorial optimization problems

Thomas Liebling
1990
Journal Articles

Résumé

We derive an asymptotic theorem generalizing in a sense the one by Beardwood et al. and Steele for the Traveling Salesman Problem, the minimun weight perfect matching problem and the minimum spanning tree problem on a random set of points in R^d, where the edge weight are taken to be equal to some power of the Euclidean distance. The rate of convergence was estimated by numerical experiments. These tend to show that for Euclidean distances, the length of the minimum spanning tree is asymptotically equal to slightly more than twice the weight of the optimum minimum perfect matching, while there seems to be a larger gap between the former and the length of the optimum traveling salesman tour.

Source officielle

https://infoscience.epfl.ch/entities/publication/5d7d0ac2-40ed-44c3-8429-b61ba6088a5d

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Thomas Liebling
1990
Journal Articles

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/5d7d0ac2-40ed-44c3-8429-b61ba6088a5d

À propos de ce résultat

Concepts associés (32)

Arbre couvrant de poids minimal

thumb|L'arbre couvrant de poids minimal d'un graphe planaire. Chaque arête est identifiée avec son poids qui, ici, est approximativement sa longueur. En théorie des graphes, étant donné un graphe non orienté connexe dont les arêtes sont pondérées, un arbre couvrant de poids minimal (ACM), arbre couvrant minimum ou arbre sous-tendant minimum de ce graphe est un arbre couvrant (sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble) dont la somme des poids des arêtes est minimale (c'est-à-dire de poids inférieur ou égal à celui de tous les autres arbres couvrants du graphe).

Euclidean distance

In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore occasionally being called the Pythagorean distance. These names come from the ancient Greek mathematicians Euclid and Pythagoras, although Euclid did not represent distances as numbers, and the connection from the Pythagorean theorem to distance calculation was not made until the 18th century.

Problème du voyageur de commerce

vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.

Afficher plus

Publications associées (2)

Asymptotics for geometric combinatorial optimization problems

Chattez avec Graph Search

Metaheuristics and Local Search

Cellular Operators in a Shared Spectrum