University of Illinois Urbana-Champaign

Cuts and partitions: solving, counting, and enumerating

Beideman, Calvin

Content Files
BEIDEMAN-DISSERTATION-2023.pdf

Permalink

https://hdl.handle.net/2142/121433

Description

Title
Cuts and partitions: solving, counting, and enumerating
Author(s)
Beideman, Calvin
Issue Date
2023-06-27
Director of Research (if dissertation) or Advisor (if thesis)
Chandrasekaran, Karthekeyan
Doctoral Committee Chair(s)
Chandrasekaran, Karthekeyan
Committee Member(s)
  • Chekuri, Chandra
  • Har-Peled, Sariel
  • Mukhopadhyay, Sagnik
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
  • Min-cut
  • Connectivity
  • Hypergraphs
  • Min-k-cut
  • Combinatorial Optimization
  • Multicriteria Optimization
Abstract
The problem of finding a global minimum cut in an undirected graph is fundamental to combinatorial optimization. It has numerous applications including network reliability, clustering, and the Travelling Salesman Problem. In addition to this computational problem, structural and enumerative aspects of minimum cuts are also foundational to representation and algorithmic results. The number of constant-approximate global minimum cuts in a connected graph is polynomial in the number of vertices. This structural result has applications in constructing cut sparsifiers, sketching and streaming algorithms, and approximation algorithms for TSP. In this thesis we consider various generalizations of the minimum cut problem. We focus on solving these variants and on counting and enumerating optimum solutions. Our results include: - A new and faster algorithm for computing connectivity in hypergraphs, - The first deterministic polynomial time algorithm for enumerating hypergraph min-$k$-cut-sets, - The first polynomial bound on the number of Multiobjective Min-cuts for a constant number of cost functions as well as the first polynomial time algorithm for enumerating all of them, and - Inapproximability results for representing symmetric submodular functions using hypergraph cut functions.
Graduation Semester
2023-08
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/121433
Copyright and License Information
Copyright 2023 Calvin Beideman

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois