Approximation algorithms for time constrained scheduling
From MaRDI portal
Publication:676776
DOI10.1006/inco.1996.2616zbMath0866.68012MaRDI QIDQ676776
Klaus Jansen, Sabine R. Öhring
Publication date: 6 July 1997
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/42dde019ed65474bf5d5ddc49d00b44b9ffefb77
68W10: Parallel algorithms in computer science
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
The maximum flow problem with disjunctive constraints, Bin packing with ``largest in bottom constraint: tighter bounds and generalizations, Online variable-sized bin packing with conflicts, Paths, trees and matchings under disjunctive constraints, Two-dimensional packing with conflicts, New lower bounds for bin packing problems with conflicts, The min-conflict packing problem, Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts, Heuristics and lower bounds for the bin packing problem with conflicts, Approximation of a batch consolidation problem, Working time constraints in operational fixed job scheduling
Cites Work
- A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm
- Precoloring extension. I: Interval graphs
- Resource constrained scheduling as generalized bin packing
- Mutual exclusion scheduling
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- Precoloring Extension III: Classes of Perfect Graphs
- On the hardness of approximating minimization problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item