Approximation Algorithms on a Scheduling Problem with Connectivity Constraints
International Journal of Foundations of Computer Science · 30.04.2026 · 1-18
DOI: 10.1142/s0129054126490043 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Foundations of Computer Science, online erschienen am 30.04.2026. Verfasst von Jiarui Xu und 3 weiteren Autor:innen. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
We propose a novel scheduling problem with connectivity constraints. This problem defines a connected graph [Formula: see text], where each edge [Formula: see text] is associated with a processing time [Formula: see text] and cost [Formula: see text], i.e., [Formula: see text], where [Formula: see text] is the set of real positive numbers. The objective is to select a path [Formula: see text] in [Formula: see text] to establish connectivity between two given vertices and further to schedule the corresponding edges on [Formula: see text] parallel machines for minimizing the sum of the makespan and the total cost. This problem is strongly NP-hard, combining elements of graph theory and parallel machine scheduling. In this paper, we focus on the uniform parallel machine environment, for which we develop approximation algorithms and provide worst-case analysis. Our results contribute to scheduling theory in combinatorial optimization and provide new insights into network restoration under resource constraints.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Xu, J., Zhang, L., Li, W., & Lin, R. (2026). Approximation Algorithms on a Scheduling Problem with Connectivity Constraints. International Journal of Foundations of Computer Science, 1-18. https://doi.org/10.1142/s0129054126490043
Vancouver
Xu J, Zhang L, Li W, Lin R. Approximation Algorithms on a Scheduling Problem with Connectivity Constraints. International Journal of Foundations of Computer Science. 2026:1-18. doi:10.1142/s0129054126490043
BibTeX
@article{Xu2026,
author = {Xu, Jiarui and Zhang, Liang and Li, Wenhua and Lin, Ran},
title = {Approximation Algorithms on a Scheduling Problem with Connectivity Constraints},
journal = {International Journal of Foundations of Computer Science},
year = {2026},
pages = {1--18},
doi = {10.1142/s0129054126490043}
}
EUVIMED