The lazy bureaucrat scheduling problem

DOI10.1016/S0890-5401(03)00060-9zbMath1026.90037OpenAlexW3098987631MaRDI QIDQ1398377

Michael A. Bender, Esther M. Arkin, Steven S. Skiena, Joseph S. B. Mitchell

Publication date: 29 July 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00060-9

zbMATH Keywords

optimizationschedulingdynamic programmingNP-completenessapproximation algorithmslazy bureaucrat

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (13)

Scheduling algorithms for procrastinators ⋮ Subset sum problems with digraph constraints ⋮ An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem ⋮ On lazy bureaucrat scheduling with common deadlines ⋮ Online lazy bureaucrat scheduling with a machine deadline ⋮ The many facets of upper domination ⋮ In)approximability of Maximum Minimal FVS ⋮ The maximum resource bin packing problem ⋮ (In)approximability of maximum minimal FVS ⋮ Hardness of lazy packing and covering ⋮ Upper Domination: Complexity and Approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for the maximum traveling salesman problem
• On approximating the longest path in a graph
• Approximating the throughput of multiple machines under real-time scheduling
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems

This page was built for publication: The lazy bureaucrat scheduling problem