Submodular Optimization with Constraints and Fairness: Algorithmic Advances and Applications

Submodular function optimization is a fundamental tool for modeling complex interactions in machine learning and graph mining. First, we study the maximization problem of the functions in the form $h = f - c$, where $f$ is a monotone, non-negative, weakly submodular function, and $c$ is a modular function. We propose a deterministic approximation algorithm that runs in ${\mathcal{O}}(\frac{n}{\epsilon}\log \frac{n}{\gamma \epsilon})$ oracle calls to $h$ and produces a solution $\Tilde{S}$ satisfying $h(\Tilde{S}) \geq \gamma(1-\epsilon)f(OPT)-c(OPT)-\frac{c(OPT)}{\gamma(1-\epsilon)}\log\frac{f(OPT)}{c(OPT)}$, where $\gamma$  is the submodularity ratio of $f$. Our algorithm offers an improved approximation guarantee compared to existing methods while achieving a lower computational complexity. Furthermore, we extend our analysis to cases where only an approximate oracle of $f$ is available.  

Submodular functions may not sufficiently capture certain complex structures, while $k$-submodular functions can effectively address this limitation. To further mitigate the solution bias, we initiate the study of fair $k$-submodular maximization and propose a $\frac{1}{3}$-approximation greedy algorithm with a runtime of $\mathcal{O}(knB)$. Our theoretical results match the best-known guarantees for non-fair $k$-submodular maximization. Furthermore, we develop a more efficient threshold-based algorithm that achieves a $(\frac{1}{3} - \epsilon)$-approximation within $\mathcal{O}(\frac{kn}{\epsilon} \log \frac{B}{\epsilon})$ function evaluations. For both algorithms, we establish approximation guarantees under settings where the $k$-submodular function is accessible only via approximate oracles.  

Across all studied problems, we extensively validate our theoretical findings through empirical studies. Our algorithms consistently exhibit substantial improvements in both objective values and computational efficiency. Moreover, our experimental results highlight the practical implications of fairness constraints, demonstrating that they do not significantly degrade solution quality.  

Committee: Dr. Pavan Aduri (co-major professor), Dr. Samik Basu (co-major professor), Dr. Chris Quinn, Dr. Mengdi Huai, and Dr. Xiaoqiu Huang