Vertex cover meets scheduling

DOI10.1007/S00453-015-9992-YzbMath1333.68209OpenAlexW2037958162MaRDI QIDQ270025

Leah Epstein, Gerhard J. Woeginger, Asaf Levin

Publication date: 6 April 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-9992-y

Mathematics Subject Classification ID

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

Related Items (2)

Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Improved Approximation Algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover

Cites Work

• Unnamed Item
• Combination of parallel machine scheduling and vertex cover
• Approximation algorithms for scheduling unrelated parallel machines
• On the hardness of approximating minimum vertex cover
• Bin packing can be solved within 1+epsilon in linear time
• The ellipsoid method and its consequences in combinatorial optimization
• An approximation algorithm for the generalized assignment problem
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• A combination of flow shop scheduling and the shortest path problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Integer Programming with a Fixed Number of Variables
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• The Competitiveness of On-Line Assignments
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Combination of Two-Machine Flow Shop Scheduling and Shortest Path Problems
• On the Relationship Between Clique-Width and Treewidth
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Vertex cover meets scheduling