6 papers
Temporal Path Covers: Dilworth Properties and Parameterized Complexity
Lapo Cioni, Sotiris Kanellopoulos, Edouard Nemery +3
The Minimum Temporal Path Cover (TPC) and Minimum Temporally Disjoint Path Cover (TDPC) problems were introduced by [Chakraborty, Dailly, Foucaud, Klasing, MFCS '24]. Both were sho…
Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis +1
The k-Visits problem is a recently introduced finite version of Pinwheel Scheduling [Kanellopoulos et al., SODA 2026]. Given the deadlines of n tasks, the problem asks whether ther…
EF(X) Orientations: A Parameterized Complexity Perspective
Sotiris Kanellopoulos, Edouard Nemery, Christos Pergaminelis +2
The concept of fair orientations in graphs was introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa in 2023, naturally modeling fair division scenarios in which resources…
Finite Pinwheel Scheduling: the k-Visits Problem
Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou +2
Pinwheel Scheduling is a fundamental scheduling problem, in which each task is associated with a positive integer , and the objective is to schedule one task per time slot…
Beer Path Problems in Temporal Graphs
Andrea D'Ascenzo, Giuseppe F. Italiano, Sotiris Kanellopoulos +3
Computing paths in graph structures is a fundamental operation in a wide range of applications, from transportation networks to data analysis. The beer path problem, which captures…
Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio
Sotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos +5
The Subset Sum Ratio problem (SSR) asks, given a multiset of positive integers, to find two disjoint subsets of such that the largest-to-smallest ratio of their sums is min…