On the Approximability of Single-Machine Scheduling with Precedence Constraints 4: Vertex Cover in Connected Graphs of Degree ≤ 3 Reduces to Weighted Vertex Cover for Interval-Order InstancesResearch Paper
In the single-machine scheduling problem , a set of jobs, each with a processing time and a weight , is processed on one machine without interruption, subject to precedence constraints given by a partial order on . The aim is to minimize the weighted sum of completion times . The problem is…