Ph.D Thesis

Ph.D StudentYovel Uri
SubjectWorst Case Analysis of Local Search Based Heuristics
DepartmentDepartment of Industrial Engineering and Management
Supervisor ASSOCIATE PROF. Asaf Levin
Full Thesis textFull thesis text - English Version


The method of local search is widely used in many hard combinatorial optimization problems. The idea is simple: start with an arbitrary (feasible) solution, and at each step, search a (relatively small) neighborhood for an improved solution. If such a solution is found, replace the current solution with it. Repeat this procedure until the neighborhood (of the current solution) contains no improving solutions. At this point, return the current solution, which is locally optimal, and terminate.

Local search algorithms are mainly used in the framework of metaheuristics, such as simulated annealing, tabu search, genetic algorithms, etc. From a practical point of view, they are usually very efficient and achieve excellent results - the generated solutions are near optimal.

However, from a theoretical point of view, there is usually no guarantee on their worst-case performance. In this dissertation, we consider the metric of approximation ratios as the tool for characterizing worst-case performance guarantees. Specifically, for a minimization (maximization) problem, A is a r-approximation algorithm if its running time is polynomial in the input size, and for any instance, apx  ≤  r ? opt  ( apx  ≥  r ? opt ), where apx is the cost of the solution produced by A and opt is the cost of an optimal solution.

The paradigm of non-oblivious local search is a modification of the standard, i.e., oblivious, local search scheme in the following sense: while the objective function of the oblivious local search is simply the given problem's, a non-oblivious local search is allowed to use a different objective function to guide the search. For some problems, this method achieves better approximation ratios than the ones obtained using oblivious local search.

In this dissertation, we further demonstrate the power of non-oblivious local search by providing such algorithms for three problems: (p,k)-Uniform Unweighted Set Cover, the Traveling Salesman Problem, and the Vehicle Routing Problem.