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:20250124T120000
DTEND;TZID=Asia/Kolkata:20250124T130000
DTSTAMP:20260924T080058
CREATED:20250109T100500Z
LAST-MODIFIED:20250219T003504Z
UID:962-1737720000-1737723600@homecse.iitd.ac.in
SUMMARY:Online\, greedy\, and conceptually simple algorithms
DESCRIPTION:Allan Borodin\, University of Toronto \nWhat can and cannot be computed by “conceptually simple algorithms”? In this regard\, my primary interest is in approximation algorithms for combinatorial optimization problems and the relation of such problems to areas such as scheduling\, algorithmic game theory and computational social choice. \nWhy do we care about conceptual simplicity\, and can we formalize such a concept? For some problems\, simple algorithmic ideas provide the best-known solution or are reasonably competitive with the best-known algorithms\, especially in the context of real data. Moreover\, “in \npractice”\, it is often the case that users will opt for a quick understandable algorithm. While it is arguably impossible to precisely define a useful general definition of “simplicity”\, we can study well-used (albeit rarely precisely defined) combinatorial algorithmic paradigms such as various forms and extensions of online and greedy algorithms\, primal-dual algorithms\, local search\, and “simple” dynamic programming. Can we then provide definitions for such paradigms that are sufficiently expressive to capture many or most existing algorithms\, but still allow us to prove impossibility results that do not rely on computational complexity assumptions? To what extent is our theoretical analysis consistent with performance in practice? We will consider the specific problem of online interval selection in different online settings. In particular\, we will consider the problem in the random order arrival model when the online algorithm can permanently reject previously accepted intervals.
URL:https://homecse.iitd.ac.in/event/allan-borodin-speaks/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR