Abstract
The Maximum Concurrent Flow Problem (MCFP) is a polynomially bounded problem that has been used over the years in a variety of applications. Sometimes it is used to attempt to find the Sparsest Cut, an NP-hard problem, and other times to find communities in Social Network Analysis (SNA) in its hierarchical formulation, the HMCFP. Though it is polynomially bounded, the MCFP quickly grows in space utilization, rendering it useful on only small problems. When it was defined, only a few hundred nodes could be solved, where a few decades later, graphs of one to two thousand nodes can still be too much for modern commodity hardware to handle.
This dissertation covers three approaches to heuristics to the MCFP that run significantly faster in practice than the LP formulation with far less memory utilization. The first two approaches are based on the Maximum Adjacency Search (MAS) and apply to both the MCFP and the HMCFP used for community detection. We compare the three approaches to the LP performance in terms of accuracy, runtime, and memory utilization on several classes of synthetic graphs representing potential real-world applications. We find that the heuristics are often correct, and run using orders of magnitude less memory and time.
Degree Date
Spring 5-2020
Document Type
Dissertation
Degree Name
Ph.D.
Department
Computer Science and Engineering
Advisor
David Matula
Second Advisor
Eli Olinick
Third Advisor
Sukumaran Nair
Fourth Advisor
Michael Hahsler
Fifth Advisor
Erik Larson
Sixth Advisor
Jeff Tian
Subject Area
Computer Science
Number of Pages
158
Format
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
Vilas, Fernando, "Heuristics for Sparsest Cut Approximations in Network Flow Applications" (2020). Computer Science and Engineering Theses and Dissertations. 12.
https://scholar.smu.edu/engineering_compsci_etds/12
