Thumbnail
Access Restriction
Subscribed

Author Kohler, Walter H. ♦ Steiglitz, Kenneth
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1974
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Branch-and-bound implicit enumeration algorithms for permutation problems (discrete optimization problems where the set of feasible solutions is the permutation group $\textit{Sn})$ are characterized in terms of a sextuple (Bp S,E,D,L,U), where (1) $\textit{Bp}$ is the branching rule for permutation problems, (2) $\textit{S}$ is the next node selection rule, (3) $\textit{E}$ is the set of node elimination rules, (4) $\textit{D}$ is the node dominance function, (5) $\textit{L}$ is the node lower-bound cost function, and (6) $\textit{U}$ is an upper-bound solution cost. A general algorithm based on this characterization is presented and the dependence of the computational requirements on the choice of algorithm parameters, S, E, D, L, and $\textit{U}$ is investigated theoretically. The results verify some intuitive notions but disprove others.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1974-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 21
Issue Number 1
Page Count 17
Starting Page 140
Ending Page 156


Open content in new tab

   Open content in new tab
Source: ACM Digital Library