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

DOI10.1051/RO:2002003zbMATH Open1005.90031OpenAlexW2030394161MaRDI QIDQ3148374FDOQ3148374

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

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

zbMATH Keywords

schedulingnon-approximabilityhierarchical communications

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• Title not available (Why is that?)
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)