Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems
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...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/61492/ |
| _version_ | 1848799882229317632 |
|---|---|
| author | Keetch, Blaine |
| author_facet | Keetch, Blaine |
| author_sort | Keetch, Blaine |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T20:42:43Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-61492 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:42:43Z |
| publishDate | 2020 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-614922025-02-28T15:02:44Z https://eprints.nottingham.ac.uk/61492/ Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems Keetch, Blaine 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. 2020-12-11 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en arr https://eprints.nottingham.ac.uk/61492/2/Blaine%20Keetch%20-%20Thesis.pdf Keetch, Blaine (2020) Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems. PhD thesis, University of Nottingham. combinatorial optimization partial differential equations Max-Cut problem Max-K-Cut problem graph theory |
| spellingShingle | combinatorial optimization partial differential equations Max-Cut problem Max-K-Cut problem graph theory Keetch, Blaine Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems |
| title | Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems |
| title_full | Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems |
| title_fullStr | Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems |
| title_full_unstemmed | Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems |
| title_short | Applying partial differential equations on networks to approximate the Max-Cut and Max-K-Cut problems |
| title_sort | applying partial differential equations on networks to approximate the max-cut and max-k-cut problems |
| topic | combinatorial optimization partial differential equations Max-Cut problem Max-K-Cut problem graph theory |
| url | https://eprints.nottingham.ac.uk/61492/ |