Characterizing sets of jobs that admit optimal greedy-like algorithms

DOI10.1007/S10951-009-0148-2zbMath1184.90176OpenAlexW1992712376MaRDI QIDQ964871

Charles W. Rackoff, Periklis A. Papakonstantinou

Publication date: 21 April 2010

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-009-0148-2

zbMATH Keywords

schedulinginterval schedulingparallel schedulingpriority algorithmsoptimal greedy algorithms

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (1)

On the Structure of Optimal Greedy Computation (for Job Scheduling)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Toward a model for backtracking and dynamic programming
• Hierarchies for classes of priority algorithms for job scheduling
• Scheduling jobs with fixed start and end times
• (Incremental) priority algorithms
• Priority algorithms for makespan minimization in the subset model.
• On the \(k\)-coloring of intervals
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Automata, Languages and Programming
• Approximation and Online Algorithms

This page was built for publication: Characterizing sets of jobs that admit optimal greedy-like algorithms