The paper proves asymptotically optimal competitive ratios for four online scheduling settings with known setup times and unknown execution times, from Θ(m) and Θ(n^{1/3}) down to Θ(log n / log log n).
Subadditive Load Balancing
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Set function optimization is essential in AI and machine learning. We focus on a subadditive set function that generalizes submodularity, and examine the subadditivity of non-submodular functions. We also deal with a minimax subadditive load balancing problem, and present a modularization-minimization algorithm that theoretically guarantees a worst-case approximation factor. In addition, we give a lower bound computation technique for the problem. We apply these methods to the multi-robot routing problem for an empirical performance evaluation.
citation-role summary
background 1
citation-polarity summary
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Scheduling on Identical Machines with Setup Time and Unknown Execution Time
The paper proves asymptotically optimal competitive ratios for four online scheduling settings with known setup times and unknown execution times, from Θ(m) and Θ(n^{1/3}) down to Θ(log n / log log n).