Computational Mathematics and Scientific Computing Seminar

---

Antibandwidth Maximization: A Map Coloring Problem

Speaker: Jennifer Scott, Rutherford Appleton Laboratory, UK

Location: Warren Weaver Hall 1302

Date: Dec. 9, 2011, 10 a.m.

Synopsis:

The antibandwidth maximization problem is the dual of the well-known bandwidth minimization problem. An interesting application is that of map coloring, where all the countries are not necessarily contiguous. In this talk, we introduce the problem and consider the feasibility of adapting heuristic algorithms for the bandwidth minimization problem to the antibandwidth maximization problem. In particular, using an inexpensive level-based heuristic we obtain an initial ordering that we refine using a hill-climbing algorithm. This approach performs well on matrices coming from a range of practical problems with underlying grids. Comparisons with existing approaches show that, on this class of problems, our algorithm can be competitive with recently reported results in terms of quality while being significantly faster.

This work is in collaboration with Yifan Hu of AT&T;