Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks

DOI10.1155/2011/476939zbMath1233.90149OpenAlexW2062851876WikidataQ58655028 ScholiaQ58655028MaRDI QIDQ666411

Rodolphe Giroudeau, Marwane Bouznif

Publication date: 8 March 2012

Published in: Advances in Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1155/2011/476939

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (1)

Erratum to ``Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks

Cites Work

• Unnamed Item
• Scheduling \(UET\)-tasks on a star network: complexity and approximation
• Complexity and approximation for precedence constrained scheduling problems with large communication delays
• UET scheduling with unit interprocessor communication delays
• On a routing problem
• Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Heuristic for a Scheduling Problem with Communication Delays
• The Parallel Evaluation of General Arithmetic Expressions
• Bounds for Certain Multiprocessing Anomalies
• An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays

This page was built for publication: Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks