F.N. Abu-Khzam, M.A. Langston, and P. Shanbhag (USA)
Algorithm Design, Parallel Computing, Optimization, Load Balancing, Applications
A novel combination of emergent algorithmic meth ods, powerful computational platforms and support ing 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 devised and implemented. The importance of maintaining a bal anced decomposition of the search space is shown to be critical to achieving scalability. With the synergis tic combination of techniques detailed here, it is now possible to solve problem instances that before were widely viewed as hopelessly out of reach. Target prob lems need only be amenable to reduction and decom position. Applications are also discussed.
Important Links:
Go Back
