Combination of parallel machine scheduling and vertex cover
From MaRDI portal
Publication:690471
DOI10.1016/j.tcs.2012.06.003zbMath1252.68354OpenAlexW2112504072MaRDI QIDQ690471
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
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