3 papers
cs.DS2026
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…
cs.DS2026
Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
Kaito Baba, Evripidis Bampis, Giorgos Mitropoulos
Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly…
cs.DS2025
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…