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:20260101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20260108T120000
DTEND;TZID=Asia/Kolkata:20260108T130000
DTSTAMP:20261010T153501
CREATED:20251225T164159Z
LAST-MODIFIED:20251225T164159Z
UID:2251-1767873600-1767877200@homecse.iitd.ac.in
SUMMARY:Online Flexible Busy Time Scheduling on Heterogeneous Machines by Gruia Calinescu
DESCRIPTION:Venue: Bharti501 \nAbstract: We study the online busy time scheduling model on heterogeneous machines. In our setting\, jobs with uniform length arrive online with a deadline that becomes known to the algorithm at the job’s arrival time. An algorithm has access to machines\, each with different associated capacities and costs. The goal is to schedule jobs on machines by their deadline\, so that the total cost incurred by the scheduling algorithm is minimized. While busy time scheduling has been well-studied\, relatively little is known when machines are heterogeneous (i.e.\, have different costs and capacities)\, despite this natural theoretical generalization being the most practical model for clients using cloud computing services. We make significant progress in understanding this model by designing an 8-competitive algorithm for the problem on unit-length jobs and provide a lower bound of 2 on the competitive ratio. The lower bound is tight in the setting when jobs form non-nested intervals. Our 8-competitive algorithm generalizes to one with competitive ratio 8(2p-1)/p < 16 when all jobs have uniform length p. \nJoint work with Sami Davies\, Samir Khuller\, and Shirley Zhang \n  \nBio: Gruia Calinescu has studied at University of Bucharest\, received his PhD in 1998 from Georgia Institute of Technology and has worked since 2000 at Illinois Tech. He has held short term positions at DIMACS\, U. Waterloo\, U. Wisconsin Milwaukee\, and Northwestern University\, and also visited the Max Plank Institute for Informatics and the Hausdorff Research Institute for Mathematics. \nHis best works (all of them improved or generalized by now) are on Multiway Cut\, Zero Extension\, and Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.
URL:https://homecse.iitd.ac.in/event/online-flexible-busy-time-scheduling-on-heterogeneous-machines-by-gruia-calinescu/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
END:VEVENT
END:VCALENDAR