VIGRE Honors Thesis Report

Thomas Maloney, Summer 2003

This summer I worked with Prof. Veit Elser to find applications of a problem solving technique he developed called the difference map. [1] The difference map is an iterative method used to solve problems whose solutions satisfy two separate constraints.

I applied the difference map to two different problems: the assignment problem and the traveling salesman problem. Efficient algorithms exist for solving the first problem, but none exists for the second. My work involved implementing the difference map in a Mathematica routine. While preliminary results show that the programs work correctly, further study is needed. In particular, I intend to compare the difference map's results to the results of other algorithms that are known to find solutions.

In the assignment problem there is a set A = {a_1, a_2, ..., a_N} of N workers and a set of B = {b_1, b_2, ..., b_N} of N jobs, and associated with each pair {a_i, b_j} there is a cost c(a_i, b_j). The goal is find the assignment of workers to jobs which minimizes cost. One can reformulate this situation as a complete bipartite graph K_{N, N}, where two sets of vertices A and B are connected by weighted edges. Finding an optimal assignment is then equivalent to finding an optimal perfect matching. The two constraints are that the edge selection be, first, a perfect matching and second, below a specified target cost.

In the traveling salesman problem, a salesman starts at one of N cities, visits every other city once, and returns to his original departure. Each city has a road to every other city, and the salesman wants to minimize his traveled distance. One can consider the set of cities as vertices in a complete graph and the roads as edges weighted by length. The salesman's goal is to find a Hamiltonian circuit with minimal weight. The two constraints are that the edge selection be, first, a Hamiltonian circuit and second, below a specified target cost.

[1] V. Elser, "Phase retrieval by iterated projections," J. Opt. Soc. Am., to appear (2003).

Last modified: October 21, 2003