Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover

DOI10.1142/S0129054117500344zbMath1387.68299OpenAlexW2789166622MaRDI QIDQ4639895

Wenyi Hong, Zhen-bo Wang

Publication date: 14 May 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054117500344

zbMATH Keywords

approximation algorithmparallel machine schedulingvertex covercombination of optimization problemslocal ratioLPT rule

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex cover meets scheduling
• Combination of parallel machine scheduling and vertex cover
• On the hardness of approximating minimum vertex cover
• The primal-dual method for approximation algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Algorithms for Scheduling Independent Tasks
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover