Combinatorial Optimization by Dynamic Contraction |
| |
Authors: | Youssef Saab |
| |
Institution: | (1) Computer Engineering and Computer Science Department, University of Missouri-Columbia, Engineering Building West, Columbia, MO, 65211 |
| |
Abstract: | A heuristic optimization methodology, Dynamic Contraction (DC), is introduced as an approach for solving a wide variety of hard combinatorial problems. Contraction is an operation that maps an instance of a problem to a smaller instance of the same problem. DC is an iterative improvement strategy that relies on contraction as a mechanism for escaping local minima. As a byproduct of contraction, efficiency is improved due to a reduction of problem size. Effectiveness of DC is shown through simple applications to two classical combinatorial problems: The graph bisection problem and the traveling salesman problem. |
| |
Keywords: | combinatorial optimization iterative improvement graph bisection number partitioning traveling salesman |
本文献已被 SpringerLink 等数据库收录! |
|