| Digital Archive


Search the Digital Archive

The Maximum Cut Problem: Investigating Computational Approaches

Show full item record

Author: Powell, Austin
Advisor: Phillips, David
Committee Members: Lewis, Michael; Kincaid, Rex K.; Torczon, Virginia
Issued Date: 2010-05-17
Subjects: Max Cut
Semidefinite Programming
Branch and Bound
URI: http://hdl.handle.net/10288/2043
Description: 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.
Degree: Bachelors of Science in Mathematics

Files in this item

Files Size Format View Description
Austin_Powell_thesis_final.pdf 243.3Kb PDF View/Open Thesis
Austin_Powell_cover.txt 638bytes Text file View/Open Cover Sheet
Austin_Powell_cover.pdf 12.57Kb PDF View/Open Cover Sheet

This item appears in the following Collection(s)

Show full item record