DATE: | Monday, June 3rd |

TIME: | 2:00 PM - 3:00 PM |

PLACE: | McConnell 320 |

TITLE: | Minimum Turn Cycle Covers in Grid Graphs |

SPEAKER: | Marco Luebbecke, Department of Mathematical Optimization, Braunschweig University of Technology |

We are given a node induced subgraph $G$ of the integer lattice (an ``orthogonal grid graph''). We seek a cycle cover of $G$, that is, a collection of cycles such that each vertex is contained in at least one cycle. The objective is to minimize the total number of bends or turns the cycles make. Each change of direction at a vertex by 90 degree counts as one turn. This problem arises as a subproblem in finding a minimum turn covering tour in grid graphs. The latter problem is known to be NP hard. We give some intuition about our problem which might enable us (but so far did not!) to prove our conjecture that the cycle cover problem be NP hard as well.

We present
natural integer programming formulations. Considering the linear
programming relaxation of one of the models we deduce conditions under
which this relaxation yields a 2-approximation algorithm. In a problem
variant, the minimum turn cycle partition problem, we require each
vertex to be contained in exactly one cycle. Here, the respective
linear programming relaxation always yields an integer solution. We
have strong evidence to conjecture that the optimal face of the
associated polytope is integral (even though the polytope itself is
not!), and we outline a possible proof. A related set partitioning
formulation of the cycle partition problem might in fact be the key to
a combinatorial polynomial time algorithm. It goes without saying, we
report on work in progress.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.

Web Address: www.cs.mcgill.ca/~beezer/Seminars/seminar99.html