BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Malin Rau (Chalmers & GU) DTSTART:20240916T111500Z DTEND:20240916T120000Z DTSTAMP:20260417T003455Z UID:cam/41 DESCRIPTION:Title: Sch eduling with Many Shared Resources\nby Malin Rau (Chalmers & GU) as pa rt of CAM seminar\n\nLecture held in MV:L14.\n\nAbstract\nConsider the man y shared resources scheduling problem where jobs have to be scheduled on i dentical parallel machines with the goal of minimizing the makespan.\nHowe ver\, each job needs exactly one additional shared resource in order to be executed and hence prevents the execution of jobs that need the same reso urce while being processed.\nPreviously\, an approximation ratio of asympt otically 2 was the best known result for this problem.\nFurthermore\, a 6/ 5-approximation for the case with only two machines was known as well as a PTAS for the case with a constant number of machines.\nWe present a simpl e and fast 5/3-approximation and a much more involved but still reasonable 1.5-approximation.\nFurthermore\, we provide a PTAS for the case with onl y a constant number of machines\, which is arguably simpler and faster tha n the previously known one\, as well as a PTAS with resource augmentation for the general case.\nThe approximation schemes make use of the N-fold in teger programming machinery\, which has found more and more applications i n the field of scheduling recently.\nIt is plausible that the latter resul ts can be improved and extended to more general cases.\nLastly\, we give a n inapproximability result for the natural problem extension where each jo b may need up to a constant number of different resources\, namely 3\, rul ing out better than 5/4 approximations for that case.\n LOCATION:https://researchseminars.org/talk/cam/41/ END:VEVENT END:VCALENDAR