The buffered work-pool approach for search-tree based optimization algorithms
Recent advances in algorithm design have shown a growing interest in seeking exact solutions to many hard problems. This new trend has been motivated by hardness of approximation results that appeared in the last decade, and has taken a great boost by the emergence of parameterized complexity theory...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/5381 http://dx.doi.org/10.1007/978-3-540-68111-3_19 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-540-68111-3_19 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513465862848512 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Rizk, Mohamad A. Abdallah, Deema A. Samatova, Nagiza F. |
| author2_role | author author author |
| author_facet | Abu-Khzam, Faisal N. Rizk, Mohamad A. Abdallah, Deema A. Samatova, Nagiza F. |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Rizk, Mohamad A. Abdallah, Deema A. Samatova, Nagiza F. |
| dc.date.none.fl_str_mv | 2017-03-17T13:33:56Z 2017-03-17T13:33:56Z 2017-03-17 |
| dc.identifier.none.fl_str_mv | 978-3-540-68111-3 http://hdl.handle.net/10725/5381 http://dx.doi.org/10.1007/978-3-540-68111-3_19 Abu-Khzam, F. N., Rizk, M. A., Abdallah, D. A., & Samatova, N. F. (2007, September). The buffered work-pool approach for search-tree based optimization algorithms. In International Conference on Parallel Processing and Applied Mathematics (pp. 170-179). Springer Berlin Heidelberg. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-540-68111-3_19 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Springer |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | The buffered work-pool approach for search-tree based optimization algorithms Parallel Processing and Applied Mathematics |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | Recent advances in algorithm design have shown a growing interest in seeking exact solutions to many hard problems. This new trend has been motivated by hardness of approximation results that appeared in the last decade, and has taken a great boost by the emergence of parameterized complexity theory. Exact algorithms often follow the classical search-tree based recursive backtracking strategy. Different algorithms adopt different branching and pruning techniques in order to reduce the unavoidable exponential growth in run time. This paper is concerned with another time-saving approach by developing new methods for exploiting high-performance computational platforms. A load balancing strategy is presented that could exploit multi-core architectures, such as clusters of symmetric multiprocessors. The well-known Maximum Clique problem is used as an exemplar to illustrate the utility of our approach. This research has been supported by the “Exploratory Data Intensive Computing for Complex Biological Systems” project from U.S. Department of Energy (Office of Advanced Scientific Computing Research, Office of Science). The work of N. F. Samatova was also sponsored by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory. Oak Ridge National Laboratory is managed by UT-Battelle for the LLC U.S. D.O.E. under contract no. DE-AC05-00OR22725. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_91c8b8fcde304c503f13d02e23319e2e |
| identifier_str_mv | 978-3-540-68111-3 Abu-Khzam, F. N., Rizk, M. A., Abdallah, D. A., & Samatova, N. F. (2007, September). The buffered work-pool approach for search-tree based optimization algorithms. In International Conference on Parallel Processing and Applied Mathematics (pp. 170-179). Springer Berlin Heidelberg. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/5381 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | Springer |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | The buffered work-pool approach for search-tree based optimization algorithmsParallel Processing and Applied MathematicsAbu-Khzam, Faisal N.Rizk, Mohamad A.Abdallah, Deema A.Samatova, Nagiza F.Recent advances in algorithm design have shown a growing interest in seeking exact solutions to many hard problems. This new trend has been motivated by hardness of approximation results that appeared in the last decade, and has taken a great boost by the emergence of parameterized complexity theory. Exact algorithms often follow the classical search-tree based recursive backtracking strategy. Different algorithms adopt different branching and pruning techniques in order to reduce the unavoidable exponential growth in run time. This paper is concerned with another time-saving approach by developing new methods for exploiting high-performance computational platforms. A load balancing strategy is presented that could exploit multi-core architectures, such as clusters of symmetric multiprocessors. The well-known Maximum Clique problem is used as an exemplar to illustrate the utility of our approach. This research has been supported by the “Exploratory Data Intensive Computing for Complex Biological Systems” project from U.S. Department of Energy (Office of Advanced Scientific Computing Research, Office of Science). The work of N. F. Samatova was also sponsored by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory. Oak Ridge National Laboratory is managed by UT-Battelle for the LLC U.S. D.O.E. under contract no. DE-AC05-00OR22725.N/ASpringer2017-03-17T13:33:56Z2017-03-17T13:33:56Z2017-03-17Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObject978-3-540-68111-3http://hdl.handle.net/10725/5381http://dx.doi.org/10.1007/978-3-540-68111-3_19Abu-Khzam, F. N., Rizk, M. A., Abdallah, D. A., & Samatova, N. F. (2007, September). The buffered work-pool approach for search-tree based optimization algorithms. In International Conference on Parallel Processing and Applied Mathematics (pp. 170-179). Springer Berlin Heidelberg.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://link.springer.com/chapter/10.1007/978-3-540-68111-3_19eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/53812021-03-19T10:03:22Z |
| spellingShingle | The buffered work-pool approach for search-tree based optimization algorithms Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | The buffered work-pool approach for search-tree based optimization algorithms |
| title_full | The buffered work-pool approach for search-tree based optimization algorithms |
| title_fullStr | The buffered work-pool approach for search-tree based optimization algorithms |
| title_full_unstemmed | The buffered work-pool approach for search-tree based optimization algorithms |
| title_short | The buffered work-pool approach for search-tree based optimization algorithms |
| title_sort | The buffered work-pool approach for search-tree based optimization algorithms |
| url | http://hdl.handle.net/10725/5381 http://dx.doi.org/10.1007/978-3-540-68111-3_19 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-540-68111-3_19 |