Please use this identifier to cite or link to this item:
http://arks.princeton.edu/ark:/88435/dsp019k41zh59c
Title: | Using Submodular Functions To Find Maximum Weighted Stable Sets |
Authors: | Bergman, Nathan |
Advisors: | Chudnovsky, Maria |
Department: | Mathematics |
Certificate Program: | Applications of Computing Program |
Class Year: | 2021 |
Abstract: | Given a set V , call a function f : 2V → R submodular if for all X, Y ⊆ V , f(X) + f(Y ) ≥ f(X ∪Y ) +f(X ∩Y ). Mathematicians have developed several versions of a combinatorial algorithm to minimize submodular functions in time polynomial in |V |, including variants by Satoru Iwata, Lisa Fleischer, and Satoru Fujishige [1], and by Alexander Schrijver [2]. These algorithms assume that there exists an oracle which can compute f(X) in polynomial time for any X ⊆ V (G). Our original goal was to extend these algorithms to multiple dimensions through a polynomialtime algorithm for coordinate-wise submodular functions (informally, functions that are submodular in each dimension). Work recently done by Maria Chudnovsky, Cemil Dibek, Daniel McGinnis, and Shira Zerbib showed that coordinate-wise submodular function minimization is NP-Hard [3]. Consequently, we switched our focus over to looking for classes of graphs where we could find a maximum weighted stable set in polynomial time by using a corresponding submodular function. Specifically, this entailed looking for special types of even sets in certain classes of graphs, where an even set is a set S ⊆ V (G) where for any u, v ∈ S, every induced path between u and v in G has even length. In particular, we looked for even sets in the line graph of a bipartite graph and for iterated even sets (even sets which partition the graph’s vertices and can be removed in iteration) in Berge graphs. |
URI: | http://arks.princeton.edu/ark:/88435/dsp019k41zh59c |
Type of Material: | Princeton University Senior Theses |
Language: | en |
Appears in Collections: | Mathematics, 1934-2023 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
BERGMAN-NATHAN-THESIS.pdf | 1.39 MB | Adobe PDF | Request a copy |
Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.