Random Trees and the Analysis of Branch and Bound Procedures

DOI10.1145/2422.322422zbMath0625.68032MaRDI QIDQ3028342

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

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

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

Related Items

Performance of linear-space search algorithms, Modeling of uplink power control for cognitive radio networks: cooperative and noncooperative, On the stochastic complexity of the asymmetric traveling salesman problem, 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, Unnamed Item