[CS] Konstantinos Ameranis Dissertation Defense/Dec 2, 2025

[via cs]

This is an announcement of Konstantinos Ameranis's Dissertation Defense.
===============================================
Candidate: Konstantinos Ameranis

Date: Tuesday, December 02, 2025

Time:  1 pm CST

Remote Location: https://uchicago.zoom.us/j/91277653173?pwd=ZUnbuQtxa7WvHX0vSVbFkY83QXh8n9.1

Location: JCL 356

Title: From Theory to Practice: Designing and Implementing Fast First-Order Algorithms for Clustering and Learning over Networks

Abstract: Clustering problems over graphs have a long history with a variety of objective functions, heuristics, and theoretical algorithms proposed. In this work, we design and explore a class of algorithms that i) lend themselves to different objective formulations and different kinds of graphs, ii) possess strong theoretical approximation and convergence properties, and iii) perform well in practice even on large-scale instances. Formally, our max-flow-based framework achieves a provable O(log n) approximation for minimum ratio cut problems by employing a cut/matching game - a popular primal/dual algorithm originally designed for undirected graphs. We show, both mathematically and empirically, how this framework can be extended to vertex-based cuts, directed graphs, and hypergraphs. In this setting, we study an application of our framework to the detection of overlapping communities in social networks. Finally, we focus on practical experimentation on the cutting player strategies and how different parameters affect the quality and running time of our framework. Using a variety of real graphs from a multitude of domains, we explore how each formulation performs. 

Advisor: Lorenzo Orecchia

Committee:  Lorenzo Orecchia, Haotian Jiang, Mladen Kolar