Improved approximation algorithm for the combination of parallel machine scheduling and vertex cover

DOI10.1142/S0129054117500344MaRDI QIDQ4639895zbMATH OpenOpenAlexFDO

Authors Wenyi Hong, Zhenbo 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 algorithmcombination of optimization problemslocal ratioLPT ruleparallel machine schedulingvertex cover

Mathematics Subject Classification ID

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

Recommendations

• Combination of parallel machine scheduling and vertex cover
• A combination of parallel machine scheduling and the covering problem
• Improved approximation algorithms for the combination problem of parallel machine scheduling and path
• Vertex cover meets scheduling
• An approximation algorithm for scheduling two parallel machines with capacity constraints.

Cites work

• A better approximation ratio for the vertex cover problem
• Algorithms for Scheduling Independent Tasks
• Approximation algorithms for NP-hard problems.
• Bounds on Multiprocessing Timing Anomalies
• Combination of parallel machine scheduling and vertex cover
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• On the hardness of approximating minimum vertex cover
• The primal-dual method for approximation algorithms
• Vertex cover meets scheduling
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(5)

• Improved approximation algorithms for the combination problem of parallel machine scheduling and path
• Vertex cover meets scheduling
• A combination of parallel machine scheduling and the covering problem
• Combination of parallel machine scheduling and vertex cover
• Vertex cover number in diverse graph architectures

This page was built for publication: Improved approximation algorithm for the combination of parallel machine scheduling and vertex cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4639895)