BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computer Science and Engineering
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20251215T120000
DTEND;TZID=Asia/Kolkata:20251215T130000
DTSTAMP:20260922T163554
CREATED:20251209T045950Z
LAST-MODIFIED:20251209T045950Z
UID:2235-1765800000-1765803600@homecse.iitd.ac.in
SUMMARY:Matroids are Equitable by Hannaneh Akrami
DESCRIPTION:Abstract: We show that if the ground set of a matroid can be partitioned into k≥2 bases\, then for any given subset S of the ground set\, there is a partition into k bases such that the sizes of the intersections of the bases with S may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabó (Electron.~J.~Comb.~2011) in the affirmative. We also investigate equitable splittings of two disjoint sets S1 and S2\, and show that there is a partition into k bases such that the sizes of the intersections with S1 may differ by at most one and the sizes of the intersections with S2 may differ by at most two; this is the best possible one can hope for arbitrary matroids. \nWe also derive applications of this result into matroid constrained fair division problems. We show that there exists a matroid-constrained fair division that is envy-free up to 1 item if the valuations are identical and tri-valued additive. We also show that for bi-valued additive valuations\, there exists a matroid-constrained allocation that provides everyone their maximin share. \nThis is based on joint work with Siyue Liu\, Roshan Raj\, and László A. Végh. \nSpeaker Bio: Hannaneh Akrami is a postdoctoral fellow at the University of Bonn and a Minerva Fast-track fellow at MPI-Informatik. She obtained her PhD from the University of Saarlandes and MPI-Informatik in 2024 and completed a BSc from Sharif University of Technology in 2019. Her interests are in fair division\, Algorithmic Game theory\, Combinatorics\, Graph theory and Approximation algorithms. \n 
URL:https://homecse.iitd.ac.in/event/matroids-are-equitable-by-hannaneh-akrami/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR