EUVIMEDEUVIMED entdecken
Crossref

Approximation Algorithms on a Scheduling Problem with Connectivity Constraints

Jiarui Xu, Liang Zhang, Wenhua Li, Ran Lin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →