Contact Information

Computer Science Department
Colgate University
McGregory Hall, 3rd Floor
13 Oak Drive
Hamilton, NY 13346
(tel) 315.228.7719
Charlotte Jablonski, Administrative Assistant

Event Detail

Department Tea: Senior Theses

Start: Tuesday, April 25, 2017, 11:30 a.m.
End: Tuesday, April 25, 2017, 12:20 p.m.
Location: 319 McGregory Hall

Speakers: Drew Zhong and Carlton Yang
Drew's Abstract:
Engineering a fast branch-and-reduce algorithm for the minimum vertex cover problem
I developed three new techniques to improve a state-of-the-art branch-and-reduce algorithm (by Akiba and Iwata, 2016) for computing an exact minimum vertex cover in larger networks such as social networks and web-crawl graphs in exact time. First, I show that we can change the order to apply slow yet critical reduction rules in a more targeted way. Second, I am able to feed the algorithm with a high-quality solution to avoid many branching calls. Third, I store solutions to subproblems to avoid repeated computations. My experiments have successfully improved the running time of this algorithm for many real-life networks, for which the existing algorithms take long time to find a solution.

Carlton's Abstract:
GPU Acceleration on Large Computational Models
Studies in regulatory biological networks often rely on mathematical modeling and computer simulations on various scales and levels of complexity. Various packages are created to provide simulation and analysis on such models, yet currently available packages do not fully meet the requirements of researchers. My research focuses on creating a software that is efficient, easily updatable and user friendly to researchers without substantial programming skills.