0

I'm interesting the NP-complete "minimum bandwidth" problem for finding the minimum bandwidth of a graph. For those not familiar, here is a link about it...

http://en.wikipedia.org/wiki/Graph_bandwidth

I've implemented the Cuthill-McKee algorithm, and this was very successful at giving me a permutation of the vertices in which the bandwidth was reduced; however, I'm looking for the minimum bandwidth, not just a reduced bandwidth that is close. If any of you have experience with this problem, what algorithms provide solutions that are the minimum and not just reduced? I don't need actual implementation of any algorithm, I just want suggestions for what algorithms to research that yield actual minimum bandwidths.

Nitrex88
  • 2,158
  • 2
  • 21
  • 23

3 Answers3

2

That's interesting problem, but when I read Wiki (your link):

Both the unweighted and weighted versions are special cases of the quadratic bottleneck assignment problem. The bandwidth problem is NP-hard, even for some special cases.[4] Regarding the existence of efficient approximation algorithms, it is known that the bandwidth is NP-hard to approximate within any constant, and this even holds when the input graphs are restricted to caterpillar trees (Dubey, Feige & Unger 2010). On the other hand, a number of polynomially-solvable special cases are known.

So wiki says it's NP-Hard to approximate it with any constant (So there is no PTAS for this problem) and your chance is just use heuristic algorithms, sure brute force algorithm works, (numbering node with numbers between 1..n randomly in startup, after that use brute force) but you should spend 1000 year to solve it for caterpillar. You should search for heuristic algorithms, not approximation and exact algorithms.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
  • a 1000 years is probably very optimistic for brute force :) – Geoffrey De Smet Apr 11 '11 at 07:30
  • Thanks for your advice. I ended up using my approximation from the Cuthill-McKee algorithm to establish an upper bound on the minimum bandwidth. I also calculate the lower bound and then brute force through all permutations only considering ones that meet specific criteria based on the bounds. It gave me a solution quick enough for the graph sizes I was using and was significantly better than sheer brute force! – Nitrex88 Apr 12 '11 at 06:31
  • @Nitrex88, good job, but you find an good heuristic or ... for your problem, not approximation, approximation means there is an approximation factor which bounds your answers worst case, some problems like this has no approximation factor, if you find an algorithm (in P) which is a polynomial approximation of brute force, you can solve NPC problems, (I said this just for learn, in this case is not important say approximation, but sometimes it's important). – Saeed Amiri Apr 12 '11 at 09:59
1

As it is NP complete you have to use some kind of "brute force" algorith. So mainly you have the different brute force as option, e.g. like branch-and-bound or linear programming (its LIP, so its in NP).

As it is NP complete you can also take every solution to a different NP complete problem (TSP, SAT,...) by transforming the problem instance from the NP-completeness proof, apply the algorith, and transform it back.

flolo
  • 15,148
  • 4
  • 32
  • 57
  • @Chris Hopman: The orignial poster wrote: `the NP-complete "minimum bandwidth"` and I had no reason to assume that he is wrong. – flolo Apr 11 '11 at 09:30
1

The simplest improvement you can do, is probably to take the result of your Cuthill-McKee algorithm and throw Tabu Search on it.

See this answer for an overview on some of the algorithms that can be applied.

Community
  • 1
  • 1
Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120