random assignment problems on 2d manifolds

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

We're Hiring!
Help Center

First page of “Random assignment problems on 2d manifolds”

Download Free PDF

Random assignment problems on 2d manifolds

2021, Journal of Statistical Physics

We consider the assignment problem between two sets of N random points on a smooth, two-dimensional manifold Ω of unit area. It is known that the average cost scales as E Ω (N) ∼ 1 2π ln N with a correction that is at most of order √ ln N ln ln N. In this paper, we show that, within the linearization approximation of the field-theoretical formulation of the problem, the first Ω-dependent correction is on the constant term, and can be exactly computed from the spectrum of the Laplace-Beltrami operator on Ω. We perform the explicit calculation of this constant for various families of surfaces, and compare our predictions with extensive numerics.

Related papers

Journal of Statistical Physics, 2019

We consider the random Euclidean assignment problem on the line between two sets of N random points, independently generated with the same probability density function 𝜚. The cost of the matching is supposed to be dependent on a power 𝑝>1 of the Euclidean distance of the matched pairs. We discuss an integral expression for the average optimal cost for 𝑁≫1 that generalizes a previous result obtained for 𝑝=2. We also study the possible divergence of the given expression due to the vanishing of the probability density function. The provided regularization recipe allows us to recover the proper scaling law for the cost in the divergent cases, and possibly some of the involved coefficients. The possibility that the support of 𝜚 is a disconnected interval is also analysed. We exemplify the proposed procedure and we compare our predictions with the results of numerical simulations.

Electronic Journal of Probability

Thèse de l'Université Paris-Saclay, 2020

Given 2𝑛 points, 𝑛 ``red'' and 𝑛 ``blue'', in a Euclidean space, solving the associated Euclidean Assignment Problem consists in finding the bijection between red and blue points that minimizes a functional of the point positions. In the stochastic version of this problem, the points are a Poisson Point Process, and some interest has developed over the years on the typical and average properties of the solution in the large 𝑛 limit. This PhD thesis investigates this problem in a number of cases (many exact results in 𝑑=1, the derivation of some fine properties in 𝑑=2, in part still conjectural, an investigation on self-similar fractals with intermediate dimensions,...). In particular, we present new contributions on the asymptotic behavior of the cost of the solution, motivated (among others) by the physics of Disordered Systems, and by results in Functional Analysis on the Monge--Kantorovich problem in the continuum.

The multidimensional assignment problem (MAP) is a NP-hard combinatorial optimization problem, occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal objective function cost of random instances of the MAP goes to zero as the problem size increases, when assignment costs are independent exponentially or uniformly distributed random variables.

In a pioneering work , Mézard and Parisi proved that methods from the theory of disordered systems at low temperature can be used to solve very difﬁcult combinatorial optimisation problems, being possible to assign an energy to their conﬁgurations and proceed with the usual apparatus of statistical mechanics. Moreover, numerical simulations showed reach behaviors that, as well as being approachable by replica calculations, opened a lot of interesting questions. Among the variety of problems that one can study in this context this work focused on the linear sum assignment problem, which can be described for example as the assignment of n tasks to n workers in such a way that the total time of execution of the tasks is minimum, being known that worker i spends tij seconds to complete the task j. The work was developed in two stages: ﬁrst it was constructed and tested a C++ implementation of the Jonker-Volgenant algorithm that solves a general linear sum assignment problem; this code was used to study the Euclidean bipartite matching problem in D dimensions, where frustration is imposed by the geometry of the ambient space, and to see how this problem reaches its mean ﬁeld approximation in the D → ∞limit (the random assignment problem), where the assignment cost is completely aleatory.

Abstract The Multidimensional Assignment Problem (MAP) is a higher-dimensional version of the Linear Assignment Problem that arises in the areas of data association, target tracking, resource allocation, etc. This paper elucidates the question of asymptotical behavior of the expected optimal value of the large-scale MAP whose assignment costs are independent identically distributed random variables with a prescribed probability distribution.

Abstract The multidimensional assignment problem (MAP) is a combinatorial problem where elements of a variable number of sets must be matched, in order to find a minimum cost solution. The MAP has applications in a large number of areas, and is known to be NP-hard. We survey some of the recent work being done in the determination of the asymptotic value of optimal solutions to the MAP, when costs are drawn from a known distribution (eg, exponential, uniform, or normal).

Physical Review E, 2017

We analytically derive, in the context of the replica formalism, the first finite size corrections to the average optimal cost in the random assignment problem for a quite generic distribution law for the costs. We show that, when moving from a power law distribution to gamma distribution, the leading correction changes both in sign and in its scaling properties. We also examine the behavior of the corrections when approaching a delta function distribution. By using a numerical solution of the saddle-point equations, we provide predictions which are very well confirmed by numerical simulations.

Probability Theory and Related Fields, 2018

We discuss the optimal matching solution for both the assignment problem and the matching problem in one dimension for a large class of convex cost functions. We consider the problem in a compact set with the topology both of the interval and of the circumference. Afterwards, we assume the points' positions to be random variables identically and independently distributed on the considered domain. We analytically obtain the average optimal cost in the asymptotic regime of very large number of points N and some correlation functions for a power-law type cost function in the form c(z) = z p , both in the p > 1 case and in the p < 0 case. The scaling of the optimal cost with the number of points is N p /2 for the assignment and N p for the matching when p > 1, whereas in both cases it is a constant when p < 0. Finally, our predictions are compared with the results of numerical simulations.

GRANDA DOSSIER , 2023

Intentionnalité en Question, 1995

List of publications 1983-2023, 2023

High-purity hydrogen production with in situ CO2 capture based on biomass gasification

The Politics of Time in China and Japan, 2022

African Journal in Education & Transformation (AJET), ISSN 2788-6379 (Print) / ISSN 3007-0171 (online), 2024

KILA Journal of Local Governance, (ISSN 2319 930X ), Vol-1, Issue-1, July-December 2014, pp. 23-30, 2014

Arqueología y Sociedad, 2006

Le théâtre musical de Luciano Berio. Sous la direction de Giordano Ferrari. Paris, L'Harmattan, 2016, 2016

Acta pharmaceutica Hungarica, 2012

Anaesthesia, Pain & Intensive Care, 2021

Marine Geology, 2013