100 citations · 657 across the 24 of their papers we have counts for
Showing 1998Show all
3 papers · 1 filter
cond-mat.stat-mech1998
Cut Size Statistics of Graph Bisection Heuristics
G. R. Schreiber, O. C. Martin
We investigate the statistical properties of cut sizes generated by heuristic algorithms which solve approximately the graph bisection problem. On an ensemble of sparse random grap…
cond-mat.dis-nn1998★ 29 cited
Comparing Mean Field and Euclidean Matching Problems
J. Houdayer, J. H. Boutet de Monvel, O. C. Martin
Combinatorial optimization is a fertile testing ground for statistical physics methods developed in the context of disordered systems, allowing one to confront theoretical mean fie…
cond-mat.dis-nn1998★ 41 cited
The stochastic traveling salesman problem: Finite size scaling and the cavity prediction
A. G. Percus, O. C. Martin
We study the random link traveling salesman problem, where lengths l_ij between city i and city j are taken to be independent, identically distributed random variables. We discuss…