Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems
Publication Date
December 11, 2020
Creator
Abstract
The Max-Cut and Max-K-Cut problems are well known combinatorial optimization problems. In this thesis we produce fast approximation methods for these problems by applying methods from partial differential equations on networks.
Given a graph G, a cut is a partition of the vertex set of G into two disjoint subsets, and a K-cut is a partition of the set into K disjoint subsets. For an unweighted graph, the size of the cut or K-cut is the number of edges which are connected by nodes belonging to distinct subsets in the partition.
We introduce the signless Ginzburg–Landau and multiclass signless Ginzburg–Landau functionals, proving that these functionals G-converge to a Max-Cut objective functional and a Max-K-Cut objective functional respectively. We approximately minimize these functionals using graph based signless Merriman–Bence–Osher schemes, which use a signless Laplacian.
We show experimentally that on some classes of graphs, the resulting algorithms produce more accurate maximum cut and maximum K-cut approximations than the current state-of-the art approximation algorithms.
In this thesis, we also prove that the graph diffusion operators of graphs G1 and G2 are isomorphic, if and only if graphs G1 and G2 are isomorphic. An isomorphism of graphs G1 and G2 is a bijection from the vertex set of G1 to the vertex set of G2, such that the bijection from the vertex sets of G1 and G2 preserves the edges of G1 and G2.
Item Type
ethesis
Thesis Type
PhD
Supervisors
Subjects (LC)
Associated Schools / Departments
School of Mathematical Sciences (UK)
eprints ID
61492
UoN Repository URI
Except where otherwise noted, this item's license is described as
File(s)![Thumbnail Image]()
Name
Blaine Keetch - Thesis.pdf
Type
Full-text
Description
Examined
Size
4.74 MB
Format
Adobe PDF
Checksum (MD5)
91703c52f6df4a8abdbd89f739bffc1b