Scalable parallel algorithms for difficult combinatorial problems

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Langston, Micheal A.
dc.contributor.author Shanbhag, Pushkar
dc.date.accessioned 2018-04-24T11:28:24Z
dc.date.available 2018-04-24T11:28:24Z
dc.date.copyright 2004 en_US
dc.date.issued 2018-04-24
dc.identifier.uri http://hdl.handle.net/10725/7514
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.title Scalable parallel algorithms for difficult combinatorial problems en_US
dc.type Conference Paper / Proceeding en_US
dc.title.subtitle a case study in optimization en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.keywords Algorithm design en_US
dc.keywords Parallel computing en_US
dc.keywords Optimization en_US
dc.keywords Load balancing en_US
dc.keywords Applications en_US
dc.identifier.ctation 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). en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.title Parallel and distributed computing and networks en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://www.semanticscholar.org/paper/Scalable-parallel-algorithms-for-difficult-A-case-Abu-Khzam-Langston/6df262f3247bb5df2d028020421fcb4c45df65c1 en_US
dc.orcid.id https://orcid.org/0000-0001-5221-8421 en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account