On penalized reload cost path, walk, tour and maximum flow: hardness and approximation

A meticulous description of a real network with respect to its heterogeneous physical infrastructure and properties is necessary for network design assessment. Quantifying the costs of making these structures work together effectively, and taking into account any hidden charges they may incur, can lead to improve the quality of service and reduce mandatory maintenance requirements, and mitigate the cost associated with finding a valid solution. For these reasons, we devote our attention to a novel approach to produce a more complete representation of the overall costs on the reload cost net-work. This approach considers both the cost of reloading due to linking structures and their internal charges, which we refer to as the penalized reload cost. We investigate the complexity and approximability of finding an optimal path, walk, tour, and maxi-mum flow problems under penalized reload cost. All these problems turn out to be NP-complete. We prove that, unless P=NP, even if the reload cost matrix is symmetric and satisfies the triangle inequality, the problem of finding a path, tour, and a maxi-mum flow with a minimum penalized reload cost cannot be approximated within any constant alpha < 2 , and finding a walk is not approximable within any factor beta <= 3.