Combination of parallel machine scheduling and vertex cover

DOI10.1016/j.tcs.2012.06.003zbMath1252.68354MaRDI QIDQ690471

Zhenhua Cui, Zhen-bo Wang

Publication date: 27 November 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.003

zbMATH Keywords

scheduling; approximation algorithm; LPT; vertex cover; local ratio; combination of optimizations

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68W25: Approximation algorithms

Related Items

Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover, Vertex cover meets scheduling, A study on several combination problems of classic shop scheduling and shortest path, Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families, On the approximability of the two-phase knapsack problem, Improved approximation algorithms for the combination problem of parallel machine scheduling and path, A combination of flow shop scheduling and the shortest path problem, Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local ratio with negative weights.
• On the hardness of approximating minimum vertex cover
• A unified approximation algorithm for node-deletion problems
• The primal-dual method for approximation algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Approximating Element-Weighted Vertex Deletion Problems for the Complete k-Partite Property
• A linear-time approximation algorithm for the weighted vertex cover problem
• Algorithms for Scheduling Independent Tasks
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• A unified approach to approximating resource allocation and scheduling