Discipline: Mathematics and Statistics
Travis Hayes - Sonoma State University
Co-Author(s): Nattapol Ploymaklam, Chiang Mai University, Chaing Mai, Thailand
The maximum cut problem is a graph theory and optimization theory problem. Although the problem is easy to understand, it is very difficult to approach. The goal of the maximum cut problem is to partition a finite graph into two disjoint groups and maximize the weight of the cut that partitions the graph. The weight of the cut is calculated by summing the weights of the vertices between the two disjoint groups. Combinatorially, there are 2n-1 unique cuts, each with their own weights, so by calculating each, one is guaranteed to find the maximum cut. The maximum cut problem has applications both inside and outside of the field of mathematics. One very common example would be from the layout of electronic circuits. It can also be used by companies and businesses to determine where their money would be best allocated to improve income on a given set of products. It can even be used to separate a workforce of individuals into two groups of equal skill. The assumptions I have made to accommodate this problem is that the graph is simple, finite, positively weighted, and undirected. That is, if two vertices are somehow related to each other, then there is exactly one relationship between the two. Additionally, there are not infinite nodes and edges on the graph and the edges have a positive weight. These assumptions make mathematical computations possible for the problem. As a control, I first created an algorithm that will insure finding the maxi- mum cut of a given graph. A graph with n vertices has exactly 2n partitions, but only 2n 1 unique cuts. The algorithm I have is able to calculate all 2n 1 cuts, but as the number of vertices increases linearly, the number of calculations increases exponentially. This algorithm I have created is valuable and necessary, as it allows me to check and compare how accurate my own personal algorithm is. My original goal for my algorithm was to be roughly 70% accurate, but much faster than the brute force method. It would have been pointless to create an algorithm that was inaccurate and slow. Through several months of collaboration with Nattapol Ploymaklam from Chiang Mai University in Thailand and testing, I have gotten my algorithm to be approximately 90% accurate and significantly faster. That is, if the maximum weight of a graph is 10x, my algorithm will calculate approximately a weight of 9x in a matter of seconds. I have been exploring the problem with non-simple graphs and directed graphs. While changing my assumption to having multiple edges between two vertices does not increase the complexity too much, allowing for the graph to be directed has been quite a challenge. I also would like to explore the possibilities of having it partition into 3 or more groups of vertices. This changes the context of the problem but seems to be the next step for my research.
Funder Acknowledgement(s): CSU-LSAMP is funded through the National Science Foundation under grant #HRD-1302873 and the Chancellor's Office of the California State University.
Faculty Advisor: Nattapol Ploymaklam, firstname.lastname@example.org
Role: I worked on this project under the help and supervision of Nattapol Ploymaklam, a Chiang Mai University Mathematics professor in Chiang Mai, Thailand. While Nattapol Ploymaklam was extremely helpful and gave me direction in where to take my project, a majority of the research and algorithm writing was done by my self. I came up with and wrote the code for my algorithm, and eventually presented my findings to students and faculty of Chiang Mai University.