A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
type: Item
instance of: scholarly article
title: A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
zbMATH Open document ID: 1026.68162
DOI: 10.1016/S0166-218X(03)00334-2
published in: Discrete Applied Mathematics
publication date: 2003-11-20T00:00:00Z
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 2006369
zbMATH Keywords: scheduling
zbMATH Keywords: single machine
zbMATH Keywords: precedence relation
zbMATH Keywords: approximation algorithm
author: N. N. Pisaruk
MaRDI profile type: Publication
cites work: Q3056948
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: 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: Maximal Closure of a Graph and Applications to Combinatorial Problems
cites work: On the structure of all minimum cuts in a network and applications
cites work: The boundaries of submodular functions
cites work: Depth-First Search and Linear Graph Algorithms
description: scientific article; zbMATH DE number 2006369