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?

$\endgroup$
  • 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 '14 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 '14 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 '14 at 11:04

Your Answer

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

Browse other questions tagged or ask your own question.