8 papers · 1 filter
The Complexity of Computing Class Probabilities in BID Probabilistic Databases
Sotiris Kanellopoulos, Ioannis Koutras, Aris Pagourtzis
We study the problem of computing class probabilities in block-independent disjoint (BID) probabilistic databases. Given the probability with which each block in the database reali…
Temporal Path Covers: Dilworth Properties and Parameterized Complexity
Lapo Cioni, Sotiris Kanellopoulos, Edouard Nemery +3
The Temporal Path Cover (TPC) and Temporally Disjoint Path Cover (TDPC) problems were introduced by [Chakraborty, Dailly, Foucaud, Klasing, MFCS '24] as the natural temporal analog…
Finite Pinwheel Covering
Sotiris Kanellopoulos
In perpetual scheduling theory, the Pinwheel Covering problem asks, given frequencies , whether there exists an infinite schedule such that every consecutive entries…
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…