Random Trees and the Analysis of Branch and Bound Procedures

DOI10.1145/2422.322422zbMATH Open0625.68032OpenAlexW2051315758MaRDI QIDQ3028342FDOQ3028342

Publication date: 1984

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2422.322422

Recommendations

scientific article; zbMATH DE number 1334602
Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
Performance of linear-space search algorithms
Branch and bound on the network model
Branch and bound on the network model

traveling salesman problem NP-hard problems discrete optimization average case complexity searching labeled trees search strategies branch and bound procedures relaxation-guided procedures

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Cited In (25)

Title not available (Why is that?)
Parallel best-first branch-and-bound in discrete optimization: a framework
Towards an abstract parallel branch and bound machine
Performance of linear-space search algorithms
An algorithm for the Lorenz measure in locational decisions on trees
A note on anomalies in parallel branch-and-bound algorithms with one-to- one bounding functions
A study of complexity transitions on the asymmetric traveling salesman problem
Title not available (Why is that?)
Estimating the Size of Branch-and-Bound Trees
A randomized parallel branch-and-bound algorithm
A branch-and-bound algorithm to solve the equal-execution-time job scheduling problem with precedence constraint and profile
On the analysis of a random walk-jump chain with tree-based transitions and its applications to faulty dichotomous search
Title not available (Why is that?)
State-Space Search
The hierarchical model of branch planning with random coefficients
Performance of linear-space search algorithms
Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
A simulation tool for the performance evaluation of parallel branch and bound algorithms
Analysis of the space of search trees under the random insertion algorithm
Lower bounds on the size of general branch-and-bound trees
Modeling of uplink power control for cognitive radio networks: cooperative and noncooperative
On the stochastic complexity of the asymmetric traveling salesman problem
On a tail bound for analyzing random trees
A note on the complexity of the asymmetric traveling salesman problem
Estimation of parameters in the tree order restriction by a randomized decision

This page was built for publication: Random Trees and the Analysis of Branch and Bound Procedures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3028342)