A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
From MaRDI portal
Publication:1414243
DOI10.1016/S0166-218X(03)00334-2zbMath1026.68162MaRDI QIDQ1414243
Publication date: 20 November 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
Partially ordered knapsack and applications to scheduling ⋮ On Submodular Search and Machine Scheduling ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ A 2-approximation algorithm for the network substitution problem
Cites Work
- Unnamed Item
- The boundaries of submodular functions
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- On the structure of all minimum cuts in a network and applications
- Maximal Closure of a Graph and Applications to Combinatorial Problems
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
