5 papers · 1 filter
Convergence and Running Time of Time-dependent Ant Colony Algorithms
Bodo Manthey, Jesse van Rhijn, Ashkan Safari +1
Ant Colony Optimization (ACO) is a well-known method inspired by the foraging behavior of ants and is extensively used to solve combinatorial optimization problems. In this paper,…
Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
Lars Rohwedder, Ashkan Safari, Tjark Vredeveld
Local search is a widely used technique for tackling challenging optimization problems, offering simplicity and strong empirical performance across various problem domains. In this…
A k-swap Local Search for Makespan Scheduling
Lars Rohwedder, Ashkan Safari, Tjark Vredeveld
Local search is a widely used technique for tackling challenging optimization problems, offering significant advantages in terms of computational efficiency and exhibiting strong e…
Additive Approximation Schemes for Load Balancing Problems
Moritz Buchem, Lars Rohwedder, Tjark Vredeveld +1
In this paper we introduce the concept of additive approximation schemes and apply it to load balancing problems. Additive approximation schemes aim to find a solution with an abso…
Smoothed Performance Guarantees for Local Search
Tobias Brunsch, Heiko Röglin, Cyriel Rutten +1
We study popular local search and greedy algorithms for scheduling. The performance guarantee of these algorithms is well understood, but the worst-case lower bounds seem somewhat…