Combination of parallel machine scheduling and vertex cover

DOI10.1016/J.TCS.2012.06.003MaRDI QIDQ690471zbMATH OpenOpenAlexFDO

Authors Zhenhua Cui, Zhenbo 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

approximation algorithmschedulingvertex coverLPTlocal 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)

Recommendations

• Improved approximation algorithm for the combination of parallel machine scheduling and vertex cover
• A combination of parallel machine scheduling and the covering problem
• Vertex cover meets scheduling
• Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem
• Single machine precedence constrained scheduling is a Vertex cover problem

Cites work

• 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 1302193 (Why is no real title available?)
• scientific article; zbMATH DE number 1833399 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• scientific article; zbMATH DE number 2119734 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A unified approach to approximating resource allocation and scheduling
• A unified approximation algorithm for node-deletion problems
• Algorithms for Scheduling Independent Tasks
• Approximating element-weighted vertex deletion problems for the complete \(k\)-partite property
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Local ratio with negative weights.
• 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 \)

Cited in

(11)

• 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
• Improved approximation algorithms for the combination problem of parallel machine scheduling and path
• A dynamic edge covering and scheduling problem: complexity results and approximation algorithms
• Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms
• On the approximability of the two-phase knapsack problem
• A combination of parallel machine scheduling and the covering problem
• Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families
• A combination of flow shop scheduling and the shortest path problem
• Parallel machine covering with limited number of preemptions

This page was built for publication: 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 Q690471)