Approximate Deadline-Scheduling with Precedence Constraints

DOI10.1007/978-3-662-48350-3_41zbMath1467.68214arXiv1507.00748OpenAlexW772046056MaRDI QIDQ3452812

Hamid Mahini, Mohammadtaghi Hajiaghyi, David Malec, Laura Sanità, Hossein Efsandiari, Jochen Könemann

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.00748

Mathematics Subject Classification ID

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

Related Items

Approximate Deadline-Scheduling with Precedence Constraints, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity results for scheduling chains on a single machine
• Fast approximation algorithm for job sequencing with deadlines
• The ellipsoid method and its consequences in combinatorial optimization
• Approximating covering integer programs with multiplicity constraints
• Approximation algorithms for covering/packing integer programs
• Better Approximation Algorithms for Technology Diffusion
• Approximate Deadline-Scheduling with Precedence Constraints
• On Column-Restricted and Priority Covering Integer Programs
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Algorithms for Scheduling Independent Tasks
• Approximation Algorithms for Certain Scheduling Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Single-Machine Scheduling with Precedence Constraints
• Scheduling