{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120258"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120258","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithms for new objectives in graph partitioning and generalizations","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_has_math":false,"creators":["Wang, Weihang"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Chandrasekaran, Karthekeyan","Balogh, József","Chekuri, Chandra","Kostochka, Alexandr"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:57Z","subjects":["Graph Partitioning","Hypergraph Partitioning","Submodular Partitioning","Algorithms","Graph Theory"],"languages":["en","eng"],"rights":["Copyright 2023 Weihang Wang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120258","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chandrasekaran, Karthekeyan","Balogh, József","Chekuri, Chandra","Kostochka, Alexandr"]},{"key":"dc:creator","label":"Author","values":["Wang, Weihang"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-04-24"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Partitioning","Hypergraph Partitioning","Submodular Partitioning","Algorithms","Graph Theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Weihang Wang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120258"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","The student, Weihang Wang, accepted the attached license on 2023-04-12 at 22:21.","The student, Weihang Wang, submitted this Dissertation for approval on 2023-04-13 at 11:59.","This Dissertation was approved for publication on 2023-04-24 at 09:11.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18965 on 2023-09-01 at 17:08:18","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithms for new objectives in graph partitioning and generalizations"]}]}],"canonical_facts":{"dc:contributor":["Chandrasekaran, Karthekeyan","Balogh, József","Chekuri, Chandra","Kostochka, Alexandr"],"dc:creator":["Wang, Weihang"],"dc:date":["2023-05","2023-04-24"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","The student, Weihang Wang, accepted the attached license on 2023-04-12 at 22:21.","The student, Weihang Wang, submitted this Dissertation for approval on 2023-04-13 at 11:59.","This Dissertation was approved for publication on 2023-04-24 at 09:11.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18965 on 2023-09-01 at 17:08:18","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120258"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Weihang Wang"],"dc:subject":["Graph Partitioning","Hypergraph Partitioning","Submodular Partitioning","Algorithms","Graph Theory"],"dc:title":["Algorithms for new objectives in graph partitioning and generalizations"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}