BARC talk by Mayank Goswami

Tuesday, August 25, 2026, 14:00-15:00, Mayank Goswami, Associate Professor at City University of New York, USA, will be giving a BARC talk on "Computing Diverse Solutions in Optimization".

Abstract:
We focus on a class of problems where the goal is to return a collection of k>=1 diverse solutions to an optimization problem P. Diversity is usually measured by either the average or the minimum distance between the returned solutions. Even when P is polynomial time solvable (i.e., finding one solution is doable in poly time), its diverse variant (finding k maximally diverse solutions) can be NP-complete, giving a rich class of challenging problems. 

The talk will begin with a survey on diverse optimization for graph problems such as spanning trees, matchings, maximum independent sets (MIS), geometric objects such as triangulations, MIS in planar graphs, knapsack and geometric knapsack, and other problems such as SAT. I will end with some recent exciting results on diverse optimization in the earth mover's metric, and on matroids. 

Bio:
Mayank Goswami is an Associate Professor at the City University of New York where he chairs the algorithms lab. His research spans theoretical ML, geometric algorithms and data structures, sorting with priced information, and diverse optimization.
He received his PhD in Applied Math from Stony Brook University and joined CUNY after a postdoc at Max-Planck Institute for Informatics.

Host:
Mikkel Vind Abrahamsen