TY - JOUR
TI - Resource Time-Sharing for IoT Applications with Deadlines
AU - Karakostas, G.
AU - Kolliopoulos, S.G.
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PY - 2022
VL - 13707 LNCS
TODO - null
SP - 91-107
PB - Springer Science and Business Media Deutschland GmbH
SN - null
TODO - 10.1007/978-3-031-22050-0_7
TODO - Internet of things, Deadline;  Generalisation;  Integrality gaps;  On-machines;  Optimisations;  Scheduling;  Time-sharing;  Time-sharing systems;  Tolerance capacity;  Weights of jobs, Approximation algorithms
TODO - Motivated by time-sharing systems with deadlines, such as 2-way synchronization of Digital Twins, we introduce the study of a very natural problem which can be abstracted as follows. We are given m machines and n jobs, as well as a set of tolerance capacities for every job j and machine i. Can we assign the jobs so that, if job j ends up on machine i, at mostjobs in total are processed on i? We define two natural optimization versions: (i) Maximize the total weight of jobs that can be assigned without violating the tolerance capacities, and (ii) minimize the amount by which capacities have to be scaled so that all jobs can be assigned. For the first problem and its generalizations we provide an -approximation algorithm. For the second problem we show that it is -inapproximable and provide linear integrality gap lower bounds for two key relaxations. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
ER -