Scalable parallel algorithms for difficult combinatorial problems
A novel combination of emergent algorithmic methods, powerful computational platforms and supporting infrastructure is described. These complementary tools and technologies are used to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very lar...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | conferenceObject |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/10725/7514 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.semanticscholar.org/paper/Scalable-parallel-algorithms-for-difficult-A-case-Abu-Khzam-Langston/6df262f3247bb5df2d028020421fcb4c45df65c1 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513482387357696 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Langston, Micheal A. Shanbhag, Pushkar |
| author2_role | author author |
| author_facet | Abu-Khzam, Faisal N. Langston, Micheal A. Shanbhag, Pushkar |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Langston, Micheal A. Shanbhag, Pushkar |
| dc.date.none.fl_str_mv | 2004 2018-04-24T11:28:24Z 2018-04-24T11:28:24Z 2018-04-24 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7514 Abu-Khzam, F. N., Langston, M. A., & Shanbhag, P. (2004). Scalable parallel algorithms for difficult combinatorial problems: A case study in optimization. In Parallel and Distributed Computing and Networks (pp. 649-654). http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.semanticscholar.org/paper/Scalable-parallel-algorithms-for-difficult-A-case-Abu-Khzam-Langston/6df262f3247bb5df2d028020421fcb4c45df65c1 |
| dc.language.none.fl_str_mv | en |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Scalable parallel algorithms for difficult combinatorial problems a case study in optimization |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | A novel combination of emergent algorithmic methods, powerful computational platforms and supporting infrastructure is described. These complementary tools and technologies are used to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are computed. To accomplish this, an efficient sequential algorithm and two forms of parallel algorithms are implemented. The importance of maintaining a balanced decomposition of the search space is shown to be critical to achieving scalability. With the synergistic combination of techniques detailed here, it is now possible to solve problem instances that before were widely viewed as hopelessly out of reach. Target problems need only be amenable to reduction and decomposition. Applications are also discussed. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_c5f823dad0fddcf71260b042a828e5a9 |
| identifier_str_mv | Abu-Khzam, F. N., Langston, M. A., & Shanbhag, P. (2004). Scalable parallel algorithms for difficult combinatorial problems: A case study in optimization. In Parallel and Distributed Computing and Networks (pp. 649-654). |
| 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/7514 |
| publishDate | 2004 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Scalable parallel algorithms for difficult combinatorial problemsa case study in optimizationAbu-Khzam, Faisal N.Langston, Micheal A.Shanbhag, PushkarA novel combination of emergent algorithmic methods, powerful computational platforms and supporting infrastructure is described. These complementary tools and technologies are used to launch systematic attacks on combinatorial problems of significance. As a case study, optimal solutions to very large instances of the NP-hard vertex cover problem are computed. To accomplish this, an efficient sequential algorithm and two forms of parallel algorithms are implemented. The importance of maintaining a balanced decomposition of the search space is shown to be critical to achieving scalability. With the synergistic combination of techniques detailed here, it is now possible to solve problem instances that before were widely viewed as hopelessly out of reach. Target problems need only be amenable to reduction and decomposition. Applications are also discussed.N/A2018-04-24T11:28:24Z2018-04-24T11:28:24Z20042018-04-24Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/7514Abu-Khzam, F. N., Langston, M. A., & Shanbhag, P. (2004). Scalable parallel algorithms for difficult combinatorial problems: A case study in optimization. In Parallel and Distributed Computing and Networks (pp. 649-654).http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://www.semanticscholar.org/paper/Scalable-parallel-algorithms-for-difficult-A-case-Abu-Khzam-Langston/6df262f3247bb5df2d028020421fcb4c45df65c1eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/75142021-03-19T10:43:12Z |
| spellingShingle | Scalable parallel algorithms for difficult combinatorial problems Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Scalable parallel algorithms for difficult combinatorial problems |
| title_full | Scalable parallel algorithms for difficult combinatorial problems |
| title_fullStr | Scalable parallel algorithms for difficult combinatorial problems |
| title_full_unstemmed | Scalable parallel algorithms for difficult combinatorial problems |
| title_short | Scalable parallel algorithms for difficult combinatorial problems |
| title_sort | Scalable parallel algorithms for difficult combinatorial problems |
| url | http://hdl.handle.net/10725/7514 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.semanticscholar.org/paper/Scalable-parallel-algorithms-for-difficult-A-case-Abu-Khzam-Langston/6df262f3247bb5df2d028020421fcb4c45df65c1 |