Random Trees and the Analysis of Branch and Bound Procedures
From MaRDI portal
Publication:3028342
DOI10.1145/2422.322422zbMath0625.68032OpenAlexW2051315758MaRDI QIDQ3028342
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
traveling salesman problemdiscrete optimizationlabeled treessearchingaverage case complexityNP-hard problemssearch strategiesbranch and bound proceduresrelaxation-guided procedures
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)
Related Items
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 note on the complexity of the asymmetric traveling salesman problem, A branch-and-bound algorithm to solve the equal-execution-time job scheduling problem with precedence constraint and profile, A study of complexity transitions on the asymmetric traveling salesman problem, On the stochastic complexity of the asymmetric traveling salesman problem, Modeling of uplink power control for cognitive radio networks: cooperative and noncooperative, Unnamed Item, Performance of linear-space search algorithms, Performance of linear-space search algorithms
