Publication

Euclidean Matching Problems and the Metropolis Algorithm

Thomas Liebling
1986
Journal Articles

Abstract

The Euclidean matching problem consist in partitionning a cloud of n points into n/2 pairs such that the sum of the euclidean distances between the endpoints of each couple is minmized, resp. maximized. In this paper the thermodynamically inspired approach of simulated annealing is applied to find good approximations to large scale problems of the above kind. Also the asymptotic behaviour of random euclidean matching problems is studied, in particular computational results on the rate of convergence towards the asymptote are given.

Official source

https://infoscience.epfl.ch/entities/publication/c1e2a20b-6b3b-4051-9f8b-e3b1dbd5fafb

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Thomas Liebling
1986
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/c1e2a20b-6b3b-4051-9f8b-e3b1dbd5fafb

About this result

Related concepts (21)

Travelling salesman problem

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP.

Computational anatomy

Computational anatomy is an interdisciplinary field of biology focused on quantitative investigation and modelling of anatomical shapes variability. It involves the development and application of mathematical, statistical and data-analytical methods for modelling and simulation of biological structures. The field is broadly defined and includes foundations in anatomy, applied mathematics and pure mathematics, machine learning, computational mechanics, computational science, biological imaging, neuroscience, physics, probability, and statistics; it also has strong connections with fluid mechanics and geometric mechanics.

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.

Related publications (5)

Euclidean Matching Problems and the Metropolis Algorithm

Chat with Graph Search

BioReason-Pro: Advancing Protein Function Prediction with Multimodal Biological Reasoning

First benchmark between the KINetic Deterministic NEutral Solver (KINDNES) and EIRENE

MATHICSE Technical Report: Reduced basis method and domain decomposition for elliptic problems in networks and complex parametrized geometries