Approximation Algorithms for Certain Scheduling Problems
From MaRDI portal
Publication:4190413
DOI10.1287/moor.3.3.197zbMath0404.90040OpenAlexW1982222968MaRDI QIDQ4190413
Oscar H. Ibarra, Chul Eung Kim
Publication date: 1978
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.3.3.197
SchedulingTreeComputational ComplexityForestPolynomial Time AlgorithmApproximation Algorithms0-1- Knapsack ProblemMaxprofitMintimeNp-Complete ProblemPrecedence GraphSingle Processor
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)
Related Items (13)
Large-scale multi-period precedence constrained knapsack problem: A mining application ⋮ Approximate Deadline-Scheduling with Precedence Constraints ⋮ Input optimization for infinite-horizon discounted programs ⋮ Integer knapsack problems with set-up weights ⋮ Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints ⋮ Clique-based facets for the precedence constrained knapsack problem ⋮ Algorithms for the bounded set-up knapsack problem ⋮ On a class of branching problems in broadcasting and distribution ⋮ Shift-and-merge technique for the DP solution of the time-constrained backpacker problem ⋮ Polyhedral results for the precedence-constrained knapsack problem ⋮ Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs ⋮ NP-Complete operations research problems and approximation algorithms ⋮ Approximations to clustering and subgraph problems on trees
This page was built for publication: Approximation Algorithms for Certain Scheduling Problems
