Title | ||
---|---|---|
On The Minimum Number Of Simplex Shapes In Longest Edge Bisection Refinement Of A Regular N-Simplex |
Abstract | ||
---|---|---|
In several areas like Global Optimization using branch-and-bound methods, the unit n-simplex is refined by bisecting the longest edge such that a binary search tree appears. This process generates simplices belonging to different shape classes. Having less simplex shapes facilitates the prediction of the further workload from a node in the binary tree, because the same shape leads to the same sub-tree. Irregular sub-simplices generated in the refinement process may have more than one longest edge when n >= 3. The question is how to choose the longest edge to be bisected such that the number of shape classes is as small as possible. We develop a Branch-and-Bound (B&B) algorithm to find the minimum number of classes in the refinement process. The developed B&B algorithm provides a minimum number of eight classes for a regular 3-simplex. Due to the high computational cost of solving this combinatorial problem, future research focuses on using high performance computing to derive the minimum number of shapes in higher dimensions. |
Year | DOI | Venue |
---|---|---|
2015 | 10.15388/Informatica.2015.36 | INFORMATICA |
Keywords | Field | DocType |
regular simplex, longest edge bisection, branch-and-bound, combinatorial optimization, simplex shape | Discrete mathematics,Mathematical optimization,Bisection,Global optimization,Supercomputer,Workload,Computer science,Binary tree,Simplex,Binary search tree | Journal |
Volume | Issue | ISSN |
26 | 1 | 0868-4952 |
Citations | PageRank | References |
3 | 0.45 | 7 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Guillermo Aparicio | 1 | 7 | 1.64 |
Leocadio G. Casado | 2 | 72 | 12.87 |
Eligius M. T. Hendrix | 3 | 139 | 26.97 |
BogláRka G.-TóTh | 4 | 9 | 1.70 |
Inmaculada García | 5 | 141 | 17.41 |