An introduction to the analysis of approximation algorithms

DOI10.1016/0166-218X(86)90059-4zbMath0593.68031OpenAlexW2101510207MaRDI QIDQ1076513

Alexander H. G. Rinnooy Kan

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90059-4

zbMATH Keywords

schedulingcombinatorial optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Algorithms in computer science (68W99)

Related Items (4)

The rate of convergence to optimality of the LPT rule ⋮ On the complexity of test case generation for NP-hard problems ⋮ Fast exact and approximate algorithms for \(k\)-partition and scheduling independent tasks ⋮ Generating hard and diverse test sets for NP-hard graph problems

Cites Work

• A new polynomial-time algorithm for linear programming
• The rate of convergence to optimality of the LPT rule
• The Asymptotic Optimality of the LPT Rule
• Algorithms for Scheduling Independent Tasks
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Unnamed Item
• Unnamed Item

This page was built for publication: An introduction to the analysis of approximation algorithms