Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs

摘要

We study the problem of routing in directed graphs with superlinear polynomial costs, which is significant for improving the energy efficiency of networks. In this problem, we are given a directed graph G(V, E) and a set of traffic demands. Routing δ_e units of demands along an edge e will incur a cost of f_e(δ_e) = μ_e(δ_e)~a with μe > 0 and α > 1. The objective is to find integral routing paths for minimizing ∑_ef_e(δ)e). Through developing a new labeling technique and applying it to a randomized reduction, we prove an Ω(((log |E|)/(log log |E|))~α ? |E|~(-(1/4))-hardness factor for this problem under the assumption that NP ?? ZPTIME(n~(Polylog(n))).