Date and Time: 03/08/2024, 14:00--15:00

Location: 25 Park Place, Room 1441

Colloquium: Independent transversals, topology and resource allocation

Speaker: Penny Haxell, University of Waterloo

Title: Independent transversals, topology and resource allocation

Abstract: An independent transversal in a vertex-partitioned graph is an
independent set that consists of exactly one vertex from each part of
the partition. Certain discrete optimization problems involving fair
allocation of resources have natural formulations in terms of the
existence of an independent transversal in a suitably defined graph.
We discuss both combinatorial and topological criteria for the existence of
independent transversals in this setting, and how they lead to efficient
approximation algorithms for resource allocation.

Host: Yi Zhao (yzhao6@gsu.edu)