Approximation algorithms for the bandwidth minimization problem for caterpillar graphs

The bandwidth minimization problem (BMP) is the problem, given a graph G and an integer k, to map the vertices of G to distinct positive integers, so that no edge of G has its endpoints mapped to integers that differ by more than k. There is no known approximation algorithm for this problem, even for the case of trees. The authors present two different approximation algorithms for the BMP for the case of special graphs, called caterpillars. The BMP for caterpillars is related to multiprocessor scheduling. It has been shown to be NP-complete, even for degree-3 trees. The authors first algorithm, gives an O(log n) times optimal algorithm, where n is the number of nodes of the caterpillar. It is based on the idea of level algorithms. The second algorithm gives an √n times approximation. It is based on a greedy approach and outperforms the first one up to a certain value n=n₀ due to the constants involved