An approximation algorithm and dynamic programming for reduction in heterogeneous environments

DOI10.1007/s00453-007-9113-7zbMath1172.68684OpenAlexW2149598202MaRDI QIDQ1024788

Da-Wei Wang, Pangfeng Liu, May-Chen Kuo

Publication date: 17 June 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9113-7

zbMATH Keywords

dynamic programmingscheduling optimizationbranch-and-bound searchheterogeneous workstation clusterreduction protocolslowest-node-first heuristic

Mathematics Subject Classification ID

Dynamic programming (90C39) Distributed systems (68M14) Approximation algorithms (68W25)

Uses Software

• MPI/MPICH
• GOTPM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A high-performance, portable implementation of the MPI message passing interface standard
• A class of solutions to the gossip problem. I
• Efficient collective communication in distributed heterogeneous systems.
• An easily implemented task-based parallel scheme for the Fourier pseudospectral solver applied to 2D Navier-Stokes turbulence.
• Broadcast Scheduling Optimization for Heterogeneous Cluster Systems
• Generalizations of broadcasting and gossiping
• A survey of gossiping and broadcasting in communication networks
• Broadcast Networks of Bounded Degree
• On the construction of minimal broadcast networks
• Designing broadcasting algorithms in the postal model for message-passing systems
• Tight Bounds on Mimimum Broadcast Networks
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A new method for constructing minimal broadcast networks