4 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…
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…