Zobrazeno 1 - 10
of 197
pro vyhledávání: '"Manthey, Bodo"'
Autor:
Manthey, Bodo, van Rhijn, Jesse
We show that the problem of counting the number of 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the
Externí odkaz:
http://arxiv.org/abs/2410.18650
We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-complete. First, we show that the Hartigan--Wong method for $k$-Means clustering is PLS-complete, even when $k = 2$. Second, we show the same resu
Externí odkaz:
http://arxiv.org/abs/2312.14916
Autor:
Manthey, Bodo, van Rhijn, Jesse
We analyze the running time of the Hartigan-Wong method, an old algorithm for the $k$-means clustering problem. First, we construct an instance on the line on which the method can take $2^{\Omega(n)}$ steps to converge, demonstrating that the Hartiga
Externí odkaz:
http://arxiv.org/abs/2309.10368
The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is exponential and
Externí odkaz:
http://arxiv.org/abs/2308.00306
Autor:
Manthey, Bodo, van Rhijn, Jesse
We analyze a tour-uncrossing heuristic for the Travelling Salesperson Problem, showing that its worst-case approximation ratio is $\Omega(n)$ and its average-case approximation ratio is $\Omega(\sqrt{n})$ in expectation. We furthermore evaluate the a
Externí odkaz:
http://arxiv.org/abs/2302.11264
Autor:
Manthey, Bodo, van Rhijn, Jesse
The 2-opt heuristic is a simple local search heuristic for the Travelling Salesperson Problem (TSP). Although it usually performs well in practice, its worst-case running time is poor. Attempts to reconcile this difference have used smoothed analysis
Externí odkaz:
http://arxiv.org/abs/2211.16908
Autor:
Manthey, Bodo, van Rhijn, Jesse
We analyze simulated annealing (SA) for simple randomized instances of the Traveling Salesperson Problem. Our analysis shows that the theoretically optimal cooling schedule of Hajek explores members of the solution set which are in expectation far fr
Externí odkaz:
http://arxiv.org/abs/2208.11444
Autor:
Klootwijk, Stefan, Manthey, Bodo
The facility location problem is an NP-hard optimization problem. Therefore, approximation algorithms are often used to solve large instances. Such algorithms often perform much better than worst-case analysis suggests. Therefore, probabilistic analy
Externí odkaz:
http://arxiv.org/abs/1903.11980
Simple heuristics often show a remarkable performance in practice for optimization problems. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot o
Externí odkaz:
http://arxiv.org/abs/1810.11232
Publikováno v:
In Discrete Applied Mathematics 31 December 2021 305:366-376
