BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260419T162028Z
UID:Seminar-dept-1340@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260313T130000
DTEND:20260313T140000
SUMMARY:School Seminar Series
DESCRIPTION:Aris Pagourtzis: Finite Pinwheel Scheduling: the k-Visits Problem\n\n Pinwheel Scheduling is a fundamental scheduling problem, in which each task is associated with a positive integer d_i, and the objective is to schedule one task per time slot, ensuring each task perpetually appears at least once in every d_i time slots. Although conjectured to be PSPACE-complete, it remains open whether Pinwheel Scheduling is NP-hard (unless a compact input encoding is used) or even contained in NP.\n\n     In this work we introduce k-Visits, a finite version of Pinwheel Scheduling, where given n deadlines, the goal is to schedule each task exactly k times. While we observe that the 1-Visit problem is trivial, we prove that 2-Visits is strongly NP-complete through a surprising reduction from Numerical 3-Dimensional Matching (N3DM). As intermediate steps in the reduction, we define NP-complete variants of N3DM which may be of independent interest. We further extend our strong NP-hardness result to a generalization of k-Visits k≥2 in which the deadline of each task may vary throughout the schedule, as well as to a similar generalization of Pinwheel Scheduling, thus making progress towards settling the complexity of Pinwheel Scheduling.\n\n     Additionally, we prove that 2-Visits can be solved in linear time if all deadlines are distinct, rendering it one of the rare natural problems which exhibit the interesting dichotomy of being in P if their input is a set and NP-complete if the input is a multiset. We achieve this through a Turing reduction from 2-Visits to a variation of N3DM, which we call Position Matching. Based on this reduction, we also show an FPT algorithm for 2-Visits parameterized by a value related to how close the input deadlines are to each other, as well as a linear-time algorithm for instances with up to two distinct deadlines.\n\n\n\nJoint work with Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou, and Euripides Markou (in SODA 2026)\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1340
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR