Date Thesis Awarded
5-2010
Access Type
Honors Thesis -- Access Restricted On-Campus Only
Degree Name
Bachelors of Science (BS)
Department
Mathematics
Advisor
David Phillips
Committee Members
Michael Lewis
Rex K. Kincaid
Virginia Torczon
Abstract
This thesis investigates various computational approaches to the Maximum Cut problem. It is generally believed that Maximum Cut cannot be solved exactly in polynomial time, so we approach the problem using various heuristics and approximation algorithms. We introduce a rank-penalization heuristic that generates feasible solutions to Maximum Cut. Numerical results show that these solutions are comparable to those given by the Goemans-Williamson randomized algorithm. We also implement a branch and bound algorithm using a branching scheme based on optimal dual variables for the Maximum Cut semidefinite programming relaxation. In our test cases, the dual branching scheme performed consistently better than randomized or largest-degree branching schemes.
Recommended Citation
Powell, Austin, "The Maximum Cut Problem: Investigating Computational Approaches" (2010). Undergraduate Honors Theses. William & Mary. Paper 744.
https://scholarworks.wm.edu/honorstheses/744
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Comments
Thesis is part of Honors ETD pilot project, 2008-2013. Migrated from Dspace in 2016.