BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T205221Z
UID:Seminar-dept-1283@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250923T130000
DTEND:20250923T140000
SUMMARY:School Seminar Series
DESCRIPTION:Neil Olver:  Nonuniform graph partitioning with just a little flex\n\nIn the nonuniform graph partitioning problem, we are given a capacitated graph G on n vertices, and numbers n_1, n_2, ..., n_t summing to n. The goal is to partition the vertices of G into parts S_1, S_2, ..., S_t with |S_i| = n_i for each i, and minimising the capacity of edges crossing between distinct parts. This generalizes, for instance, the well-known graph bisection problem.\n\n\n\nIn order to obtain positive results, it is necessary to consider a bicriteria approximation, where we allow part sizes to be violated by a multiplicative factor r (i.e., |S_i|  0 (Feldmann and Foscini 2011, Andreev and Raecke 2008). Krauthgamer, Naor, Schwartz and Talwar (2014) showed an O(log n) approximation for the nonuniform problem for any r >= 1, but 1 is a particular barrier to their techniques. We overcome this barrier to give an an O(log n) approximation for any constant r > 0.\n\n\n\n(Joint work with Harald Raecke and Stefan Schmid.) \n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1283
LOCATION:ELEC201, 2th Floor Lecture Theater EEE
END:VEVENT
END:VCALENDAR