Approximation Algorithms for Certain Scheduling Problems

DOI10.1287/MOOR.3.3.197MaRDI QIDQ4190413zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

SchedulingTreeComputational ComplexityForestPolynomial Time AlgorithmApproximation Algorithms0-1- Knapsack ProblemMaxprofitMintimeNp-Complete ProblemPrecedence GraphSingle Processor

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cited in

(14)

• Polyhedral results for the precedence-constrained knapsack problem
• Algorithms for the bounded set-up knapsack problem
• Input optimization for infinite-horizon discounted programs
• Integer knapsack problems with set-up weights
• Clique-based facets for the precedence constrained knapsack problem
• Large-scale multi-period precedence constrained knapsack problem: a mining application
• On a class of branching problems in broadcasting and distribution
• Shift-and-merge technique for the DP solution of the time-constrained backpacker problem
• Approximate Deadline-Scheduling with Precedence Constraints
• Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
• Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs
• NP-Complete operations research problems and approximation algorithms
• Integrated operating room scheduling and surgical instrument inventory management: models, algorithms, and cost-saving insights
• Approximations to clustering and subgraph problems on trees

This page was built for publication: Approximation Algorithms for Certain Scheduling Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4190413)