On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications

DOI10.1051/RO:2002003MaRDI QIDQ3148374zbMATH OpenOpenAlexFDO

Authors Rodolphe Giroudeau, Evripidis Bampis, Jean-Claude König

Publication date 30 September 2002

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=RO_2002__36_1_21_0, https://eudml.org/doc/105259, https://semanticscholar.org/paper/216befa75545433f94d4ead1b543a0224d33a84c

zbMATH Keywords

schedulingnon-approximabilityhierarchical communications

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• scientific article; zbMATH DE number 1500535
• Bicriteria approximation algorithms for scheduling problems with communications delays
• scientific article; zbMATH DE number 2090586
• Scheduling \(UET\)-tasks on a star network: complexity and approximation
• Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302193 (Why is no real title available?)
• scientific article; zbMATH DE number 1016640 (Why is no real title available?)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Three, four, five, six, or the complexity of scheduling with communication delays

Cited in

(4)

• An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications
• Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks
• General scheduling non-approximability results in presence of hierarchical communications
• An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications.

This page was built for publication: On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications

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