12th January 2007: Guest lecture: The Snowblower Problem
by Valentin Polishchuk, Department of Applied Mathematics & Statistics, Stony Brook University, New York
on Friday 12th January at 10:15 Exactum, room B222
Abstract: We study variations of the traveling salesperson problem in grid graphs. We introduce the snowblower problem -- a new optimization problem in which the objective is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). We show that in general, the problem is NP-complete, and we present polynomial-time constant-factor approximation algorithms for removing snow under various assumptions about the operation of the snowblower. We consider also the online version of the problem, which is closely related to data collection in sensor networks. For the case of collecting the data in a regular square grid we provide competitive analysis of an online algorithm for the problem. Finally, considering different shapes of the snowblowing tool leads to studying the Hamiltonian Cycle problem in triangular grid graphs. We prove that in general, the problem is NP-complete, and that the grids without "local cuts" are (almost) always Hamiltonian. Our results are applicable to triangulated manifolds whose connectivity is greater than the connectivity of a regular triangular mesh; this suggests an efficient scheme for rendering the triangulation data in a graphics engine.
WELCOME!