8
$\begingroup$

Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching vector, and recently developed techniques such as measure-and-conquer may help us to obtain a better bound. While branch-and-bound algorithms are usually used in practice and seem more efficient (in my experience), I find no result of analyzing the worst-case time complexity of a branch-and-bound algorithm. Does anyone know such an example?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ My guess is that branch-and-bound algorithms typically have very bad worst case behavior, but for various reasons perform well in practice. In TCS we're mostly interested in worst case behavior, both since it's easier to define and analyze, and because our complexity classes are defined in this way. $\endgroup$
    – Yuval Filmus
    Dec 18, 2014 at 5:37
  • $\begingroup$ Branching algorithms are hard to analyze. So far we have no good enough tool, and all results are only upper bounds. Prof. Dieter Kratsch, who is one of the authors of the book Exact Exponential Algorithm, said that no such bound has been shown to be tight in his speech last week. Of course it is not impossible. Such an analysis, if it exists, must depend on some properties of the lower bound function used in the algorithm. I do not expect a general approach but just looking for an example. $\endgroup$
    – Bangye
    Dec 18, 2014 at 6:29
  • 3
    $\begingroup$ Lower bounds are only known in a rather restricted models of branch-and-bound, where either branching is simple or bounding is restricted. See e.g. this or this and the literature therein. $\endgroup$
    – Stasys
    Dec 22, 2014 at 11:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.