  This paper investigates the intractability of large-scale combinatorial
optimization with multi-start methods. For the theoretical performance
analysis, we focus on the random multi-start (RMS) method, one of the
representative multi-start methods including the RMS local search and the
greedy randomized adaptive search procedure (GRASP). Our main theoretical
contribution is to derive two power-law formulas using extreme value theory.
One is for the expected improvement rate (EIR) of the best empirical objective
value (EOV), and the other is for the expected relative gap (ERG) of the best
EOV to the supremum of empirical objective values. Notably, the ERG has
scale-freeness as a function of the number of iterations. Thus, the
``half-life" of the ERG is eventually proportional to the number of iterations
completed by an RMS algorithm. This result can be understood as the curse of
scale-freeness: a Zeno's paradox-like phenomenon of ``trying to get to the goal
pushes it far away," Through numerical experiments, we observe that applying
several RMS algorithms to traveling salesman problems is subject to the curse
of scale-freeness. Furthermore, we show that overcoming the curse of
scale-freeness requires the development of an algorithm with exponentially
accelerated performance compared to the RMS method.
