The Runtime of Random Local Search on the Generalized Needle Problem
In their recent work, C. Doerr and Krejca (Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search heuristic on generalized Needle functions. Based on these upper bounds, they deduce in a not fully rigorous manner a drastic influence of the needle radius $k$ on the runtime. In this short article, we add the missing lower bound necessary to determine the influence of parameter $k$ on the runtime. To this aim, we derive an exact description of the expected runtime, which also significantly improves the upper bound given by C. Doerr and Krejca. We also describe asymptotic estimates of the expected runtime.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nerve Block Target Localization and Needle Guidance for Autonomous Robotic Ultrasound Guided Regional Anesthesia
Visual servoing for the development of autonomous robotic systems capable of administering UltraSound (US) guided regional anesthesia requires real-time segmentation of nerves, needle tip localization and needle trajecto…
Anatomyobject-detectionObject DetectionObject Tracking+1Using Sequential Runtime Distributions for the Parallel Speedup Prediction of SAT Local Search
This paper presents a detailed analysis of the scalability and parallelization of local search algorithms for the Satisfiability problem. We propose a framework to estimate the parallel performance of a given algorithm b…
Markerless Suture Needle 6D Pose Tracking with Robust Uncertainty Estimation for Autonomous Minimally Invasive Robotic Surgery
Suture needle localization is necessary for autonomous suturing. Previous approaches in autonomous suturing often relied on fiducial markers rather than markerless detection schemes for localizing a suture needle due to …
Pose TrackingExpected Runtime Comparisons Between Breadth-First Search and Constant-Depth Restarting Random Walks
When greedy search algorithms encounter a local minima or plateau, the search typically devolves into a breadth-first search (BrFS), or a local search technique is used in an attempt to find a way out. In this work, we f…
A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman Problem
The Travelling Salesman Problem (TSP) is one of the most popular Combinatorial Optimization Problem. It is well solicited for the large variety of applications that it can solve, but also for its difficulty to find optim…
Combinatorial Optimization