Comparing two Probabilistic Models of the Computational Complexity of the Branch and Bound Algorithm.
Michèle DionMarc GenglerStéphane UbédaPublished in: CONPAR (1994)
Keyphrases
- branch and bound algorithm
- probabilistic model
- computational complexity
- np hard
- lower bound
- branch and bound
- upper bound
- test problems
- graphical models
- optimal solution
- lower bounding
- combinatorial optimization
- search tree
- np complete
- randomly generated problems
- upper bounding
- precedence constraints
- single machine scheduling problem
- max sat
- variable ordering
- conditional random fields
- finding an optimal solution
- mixed integer linear programming
- special case
- bayesian networks
- expectation maximization
- worst case
- branch and bound method
- neural network
- lagrangian relaxation
- mathematical programming
- approximation algorithms
- knapsack problem
- objective function
- maximum clique