Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01bv73c3516
Title: The Query Complexity of Approximating Max-Cut in the Value Oracle Model
Authors: Ragavan, Seyoon
Advisors: Weinberg, S. Matthew
Department: Mathematics
Certificate Program: Applications of Computing Program
Class Year: 2021
Abstract: This thesis considers the problem of global max-cut on a weighted undirected graph in the \emph{value oracle model}. In this model, the algorithm does not have direct access to the graph and instead only has access to an oracle that can answer queries about the value of any cut. The algorithm's cost is simply the number of queries made. This model arises as a natural special case of submodular function maximisation with a value oracle. We consider both deterministic and randomised algorithms, and investigate the query complexity of achieving a $c$-approximation for any positive $c \leq 1$. We make substantial progress towards identifying the query complexity for all values of $c$ and both the deterministic and randomised settings up to logarithmic factors. We observe a ``phase transition" analogous to general submodular function maximisation at $c = 1/2$, where the complexity of solving the problem for $c > 1/2$ is much harder than solving it for $c < 1/2$. Specifically, we show that achieving a $c$-approximation can be done with $O(\log n)$ queries when $c < 1/2$ but requires at least $O(n/\log n)$ queries when $c > 1/2$. We also observe what could be an additional jump at $c = 1$, showing that deterministic algorithms require at least $\Omega(n^2)$ queries to find the exact value of the max cut.
URI: http://arks.princeton.edu/ark:/88435/dsp01bv73c3516
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2021

Files in This Item:
File Description SizeFormat 
RAGAVAN-SEYOON-THESIS.pdf438.1 kBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.