Approximating interval selection on unrelated machines with unit-length intervals and cores

DOI10.1007/978-3-319-45587-7_30MaRDI QIDQ2835690zbMATH OpenOpenAlexFDO

Authors Kateřina Böhmová, Enrico Kravina, Matúš Mihalák

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-45587-7_30

zbMATH Keywords

computational complexityinterval selectionapproximation algorithmsfixed-interval scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Interval selection with machine-dependent intervals
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Interval scheduling on related machines
• scientific article; zbMATH DE number 2119734
• Interval selection: Applications, algorithms, and lower bounds

Cites work

• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Complexity results for scheduling tasks with discrete starting times
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Interval scheduling on identical machines
• Interval scheduling: A survey
• Interval selection with machine-dependent intervals
• Maximizing weighted number of just-in-time jobs on unrelated parallel machines
• On the approximability of an interval scheduling problem
• On the complexity of scheduling tasks with discrete starting times
• Scheduling jobs with fixed start and end times

Cited in

(2)

• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Interval selection with machine-dependent intervals

This page was built for publication: Approximating interval selection on unrelated machines with unit-length intervals and cores

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