McGill University - School of Computer Science

Algorithms Seminar 2002

Everybody is welcome!

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