Technion, IEM faculty - Operations Research seminar Speaker: Uri Yovel, Technion Title: Worst case analysis of local search based heuristics Date: 11/06/2012 Time: 12:30 Place: Bloomfield-527 Abstract: <http://ie.technion.ac.il/seminar_files/1337072859_seminarOR_Uri.doc> Or read it here, more or less: The traveling salesman problem (TSP) and the vehicle routing problem (VRP) are classical NP-hard problems in combinatorial optimization. The k-opt heuristics are among the most common techniques for approaching TSP. They are used either directly or as subroutines in more sophisticated heuristics, such as the celebrated Lin-Kernighan heuristic. The value of k is typically 2 or 3. In this paper, we modify the 2-opt heuristic to be based on a function f of the distances rather than the distances solely. This may be viewed as modifying the local search with the 2-change neighborhood to be non-oblivious. We denote the corresponding heuristic by (2,f)-opt. We provide theoretical performance guarantees for it: both lower and upper bounds based on the ones given by Chandra, Karloff, and Tovey (1999), obtained originally for the standard 2-opt heuristic; the upper bound is improved by a factor of v2 with respect to the known upper bound of the standard 2-opt. We then provide experimental evidence based on TSPLIB benchmark problems, showing that (2,f)-opt with f(x) = x^r < 1 significantly outperforms 2-opt. We then briefly discuss a local search algorithm for the VRP; in particular, we show that the k-opt heuristic is not strong enough to guarantee a constant approximation ratio, and we present a different (non-oblivious) local search whose approximation ratio is 2. To the best of our knowledge, this is the first local search algorithm for this problem with proved performance guarantee. Uri Yovel – PhD candidate Advisor: Asaf Levin Faculty of Industrial Engineering and Management, Technion --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: <ehazan@ie.technion.ac.il>