The stochastic matching problem

Abstract

The matching problem plays a basic role in combinatorial optimization and in statistical mechanics. In its stochastic variants, optimization decisions have to be taken given only some probabilistic information about the instance. While the deterministic case can be solved in polynomial time, stochastic variants are worst-case intractable. We propose an efficient method to solve stochastic matching problems which combines some features of the survey propagation equations and of the cavity method. We test it on random bipartite graphs, for which we analyze the phase diagram and compare the results with exact bounds. Our approach is shown numerically to be effective on the full range of parameters, and to outperform state-of-the-art methods. Finally we discuss how the method can be generalized to other problems of optimization under uncertainty.

Published version has very minor changes

Cited by in corpus (17)

• Spreading dynamics in complex networks
• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• Containing epidemic outbreaks by message-passing techniques
• Control of Multilayer Networks
• Optimizing spread dynamics on graphs by message passing
• Large deviations of cascade processes on graphs
• Quadratic stochastic Euclidean bipartite matching problem
• Stochastic optimization by message passing
• Phase transition for cutting-plane approach to vertex-cover problem
• Sign problem in the Bethe approximation
• One-loop diagrams in the Random Euclidean Matching Problem
• Cavity approach to variational quantum mechanics
• Low-temperature excitations within the Bethe approximation
• Coordination problems on networks revisited: statics and dynamics
• The Random Fractional Matching Problem
• Statistical Physics of Medical Diagnostics: Study of a Probabilistic Model
• State assignment problem in systems biology and medicine: on the importance of state interaction network topology