Algorithms for new objectives in graph partitioning and generalizations

Wang, Weihang

Permalink

https://hdl.handle.net/2142/120258 Copy

Description

Title

Algorithms for new objectives in graph partitioning and generalizations

Author(s)

Wang, Weihang

Issue Date

2023-04-24

Director of Research (if dissertation) or Advisor (if thesis)

Chandrasekaran, Karthekeyan

Doctoral Committee Chair(s)

Balogh, József

Committee Member(s)

• Chekuri, Chandra
• Kostochka, Alexandr

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Graph partitioning
• Hypergraph partitioning
• Submodular partitioning
• Algorithms
• Graph theory

Abstract

In this thesis, we consider a class of graph partitioning problems: The input consists of a graph and a positive integer k, and the goal is to partition the vertex set of the graph into k parts while satisfying certain constraints in order to optimize an objective of interest. Varying constraints and objectives lead to a wide variety of graph partitioning problems. The classic Graph-MinCut and Graph-Min-(s,t)-Cut problems can be viewed as special cases of these problems. The study of these problems has led to novel algorithmic techniques and structural results as well as developed connections between graph theory and algorithms. Graph partitioning problems further generalize to hypergraph and submodular partitioning problems. In this thesis, we investigate new objectives in graph and hypergraph partitioning and long-standing objectives in submodular partitioning. We advance both algorithmic and structural aspects of the associated partitioning problems. We show hardness results for several graph partitioning problems under new objectives. We design approximation algorithms and fixed-parameter approximation scheme to solve these graph partitioning problems. We prove new structural results for graphs and hypergraphs that lead to polynomial-time algorithms to enumerate all optimum solutions of certain graph/hypergraph partitioning problems. We analyze the approximation factor of a classic algorithm for submodular partitioning based on principle partition sequence for monotone, symmetric, and posimodular submodular function families.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Weihang Wang

Owning Collections