Single machine precedence constrained scheduling is a Vertex cover problem
type: Item
instance of: scholarly article
title: Single machine precedence constrained scheduling is a Vertex cover problem
zbMATH Open document ID: 1183.68102
author: Christoph Ambühl
author: Monaldo Mastrolilli
published in: Algorithmica
publication date: 2009-05-06T00:00:00Z
Mathematics Subject Classification ID: 68M20
zbMATH DE Number: 5551244
zbMATH Keywords: algorithms
zbMATH Keywords: scheduling
zbMATH Keywords: vertex cover
MaRDI profile type: Publication
full work available at URL: s00453-008-9251-6
OpenAlex ID: W2093392878
cites work: Approximating Precedence-Constrained Single Machine Scheduling by Coloring
cites work: Scheduling with Precedence Constraints of Low Fractional Dimension
cites work: Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
cites work: Partial orders of dimension 2
cites work: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
cites work: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
cites work: Single-Machine Scheduling with Precedence Constraints
cites work: On the hardness of approximating minimum vertex cover
cites work: Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
cites work: Some optimal inapproximability results
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Q4411395
cites work: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
cites work: Complexity of Scheduling under Precedence Constraints
cites work: Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
cites work: Q4918387
cites work: Properties of vertex packing and independence system polyhedra
cites work: Vertex packings: Structural properties and algorithms
cites work: A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
cites work: An algorithm for the single machine sequencing problem with precedence constraints
cites work: Polynomial time approximation algorithms for machine scheduling: Ten open problems
cites work: Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
cites work: Single Machine Scheduling with Precedence Constraints of Dimension 2
cites work: Q4004146
cites work: On the approximability of average completion time scheduling under precedence constraints.
DOI: 10.1007/S00453-008-9251-6
Recommended article: Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem
Recommended article: Single-Machine Scheduling with Precedence Constraints
Recommended article: Single-Machine Scheduling Polyhedra with Precedence Constraints
Recommended article: On the approximability of single-machine scheduling with precedence constraints
Recommended article: An exact algorithm for the precedence-constrained single-machine scheduling problem
Recommended article: Integer Programming and Combinatorial Optimization
Recommended article: Q3204309
Recommended article: Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
Recommended article: Q4538153
Recommended article: Q4494459
description: scientific article; zbMATH DE number 5551244