3
$\begingroup$

I am solving a graph problem, which can be formulated as an integer programme. Based on computer experiments, it seems that the branch and bound method works well. I would like to analyse the running time, and wonder whether there have been other problems where branch and bound method was used and the theoretical bounds on the running time has been established?

On another note, if anyone knows any examples of problems where the range of possible values that a variable in a linear programme can take, I'd also be interested in.

Improve this question
$\endgroup$
1
$\begingroup$

Branch-and-bound is a heuristic. In this context, my impression is that typically analysis of the worst-case running time of such heuristics is not enlightening: the worst-case running time is typically exponential. On some problems in practice branch-and-bound may run significantly faster than that, but my sense is that worst-case running time analysis usually isn't very helpful for predicting when that will happen.

Improve this answer
$\endgroup$
1
$\begingroup$

A good example of non-trivial algorithmic analysis of a practical braching algorithm is the vertex cover problem. It can be proven that if the answer is $k$, then a simple branching algorithm has time complexity $O(2^k n)$. The analysis uses "bounded search tree" technique.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm looking for an example of linear programming, but this is also a good example of the branching method in general. Thanks. $\endgroup$ – Hung H Jan 25 '20 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.