<p>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?</p>

CC BY-SA 3.0
2014-12-18T05:37:36.513Z
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.
Yuval Filmus
CC BY-SA 3.0
2014-12-18T06:29:35.523Z
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.
Bangye
CC BY-SA 3.0
2014-12-22T11:04:19.887Z
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](http://www.sciencedirect.com/science/article/pii/S0304397511005913) or [this](http://www.sciencedirect.com/science/article/pii/S0167637709001333) and the literature therein.
Stasys
<cc.complexity-theory><ds.algorithms><time-complexity>
Time complexity of a branching-and-bound algorithm
Bangye
# Time complexity of a branching-and-bound algorithm

(Asked by: username_0 on 2014-12-18)

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?

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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](http://www.sciencedirect.com/science/article/pii/S0304397511005913) or [this](http://www.sciencedirect.com/science/article/pii/S0167637709001333) and the literature therein.  

---

## 0 answers

