Random Trees and the Analysis of Branch and Bound Procedures

DOI10.1145/2422.322422MaRDI QIDQ3028342zbMATH OpenOpenAlexFDO

Authors Douglas R. Smith

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

zbMATH Keywords

average case complexitybranch and bound proceduresdiscrete optimizationlabeled treesNP-hard problemsrelaxation-guided proceduressearch strategiessearchingtraveling salesman problem

Mathematics Subject Classification ID

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

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

Cited in

(25)

• A note on anomalies in parallel branch-and-bound algorithms with one-to- one bounding functions
• A simulation tool for the performance evaluation of parallel branch and bound algorithms
• 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
• A note on the complexity of the asymmetric traveling salesman problem
• On a tail bound for analyzing random trees
• The hierarchical model of branch planning with random coefficients
• A study of complexity transitions on the asymmetric traveling salesman problem
• Lower bounds on the size of general branch-and-bound trees
• An algorithm for the Lorenz measure in locational decisions on trees
• Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
• Analysis of the space of search trees under the random insertion algorithm
• scientific article; zbMATH DE number 1334602 (Why is no real title available?)
• On the analysis of a random walk-jump chain with tree-based transitions and its applications to faulty dichotomous search
• State-Space Search
• scientific article; zbMATH DE number 1444332 (Why is no real title available?)
• scientific article; zbMATH DE number 1456964 (Why is no real title available?)
• Estimating the Size of Branch-and-Bound Trees
• Estimation of parameters in the tree order restriction by a randomized decision
• Performance of linear-space search algorithms
• Performance of linear-space search algorithms
• Modeling of uplink power control for cognitive radio networks: cooperative and noncooperative
• Towards an abstract parallel branch and bound machine
• Parallel best-first branch-and-bound in discrete optimization: a framework
• On the stochastic complexity of the asymmetric traveling salesman problem

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)