Combination of parallel machine scheduling and vertex cover

DOI10.1016/j.tcs.2012.06.003zbMath1252.68354OpenAlexW2112504072MaRDI 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

schedulingapproximation algorithmLPTvertex coverlocal ratiocombination of optimizations

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items

Vertex cover meets scheduling, Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families, A study on several combination problems of classic shop scheduling and shortest path, Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms, Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover, 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

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