@inproceedings{d82a740870254ea9ab5d2520d41fe6bd,
title = "Hardness of routing for minimizing superlinear polynomial cost in directed graphs",
abstract = "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 (formula presented) units of demands along an edge e will incur a cost of (formula presented). The objective is to find integral routing paths for minimizing (formula presented). Through developing a new labeling technique and applying it to a randomized reduction, we prove an (formula presented) hardness factor for this problem under the assumption that (formula presented).",
keywords = "Directed graphs, Hardness of approximation, Network energy effciency, Superlinear polynomial cost",
author = "Yangguang Shi and Fa Zhang and Zhiyong Liu",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 ; Conference date: 20-04-2017 Through 22-04-2017",
year = "2017",
doi = "10.1007/978-3-319-55911-7_41",
language = "English",
isbn = "9783319559100",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "571--585",
editor = "Gerhard Jager and Silvia Steila and T.V. Gopal",
booktitle = "Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings",
address = "Germany",
}
