Approximability and Non-approximability of the Minimum Block Transfer Problem

摘要

The paper deals with the following problem: Given a directed acyclic graph, the objective is to find a mapping of its nodes into blocks of size at most B that minimizes the maximum number of external arcs during traveraals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. The problem can be shown to be NP-hard.