Hardness of routing for minimizing superlinear polynomial cost in directed graphs

Yangguang Shi; Fa Zhang; Zhiyong Liu

doi:10.1007/978-3-319-55911-7_41

Hardness of routing for minimizing superlinear polynomial cost in directed graphs

Yangguang Shi, Fa Zhang, Zhiyong Liu^*

^*此作品的通讯作者

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

摘要

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).

源语言	英语
主期刊名	Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
编辑	Gerhard Jager, Silvia Steila, T.V. Gopal
出版商	Springer Verlag
页	571-585
页数	15
ISBN（印刷版）	9783319559100
DOI	https://doi.org/10.1007/978-3-319-55911-7_41
出版状态	已出版 - 2017
已对外发布	是
活动	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, 瑞士期限: 20 4月 2017 → 22 4月 2017

出版系列

姓名	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
卷	10185 LNCS
ISSN（印刷版）	0302-9743
ISSN（电子版）	1611-3349

会议

会议	14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
国家/地区	瑞士
市	Bern
时期	20/04/17 → 22/04/17

联合国可持续发展目标

此成果有助于实现下列可持续发展目标：

访问文件

10.1007/978-3-319-55911-7_41

其它文件与链接

链接到 Scopus 的出版物

引用此

Shi, Y., Zhang, F., & Liu, Z. (2017). Hardness of routing for minimizing superlinear polynomial cost in directed graphs. 在 G. Jager, S. Steila, & T. V. Gopal (编辑), Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings (页码 571-585). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 10185 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-55911-7_41

Shi, Yangguang ; Zhang, Fa ; Liu, Zhiyong. / Hardness of routing for minimizing superlinear polynomial cost in directed graphs. Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. 编辑 / Gerhard Jager ; Silvia Steila ; T.V. Gopal. Springer Verlag, 2017. 页码 571-585 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

}

Shi, Y, Zhang, F & Liu, Z 2017, Hardness of routing for minimizing superlinear polynomial cost in directed graphs. 在 G Jager, S Steila & TV Gopal (编辑), Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 卷 10185 LNCS, Springer Verlag, 页码 571-585, 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, Bern, 瑞士, 20/04/17. https://doi.org/10.1007/978-3-319-55911-7_41

Hardness of routing for minimizing superlinear polynomial cost in directed graphs. / Shi, Yangguang; Zhang, Fa; Liu, Zhiyong.
Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. 编辑 / Gerhard Jager; Silvia Steila; T.V. Gopal. Springer Verlag, 2017. 页码 571-585 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 10185 LNCS).

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

TY - GEN

T1 - Hardness of routing for minimizing superlinear polynomial cost in directed graphs

AU - Shi, Yangguang

AU - Zhang, Fa

AU - Liu, Zhiyong

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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).

AB - 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).

KW - Directed graphs

KW - Hardness of approximation

KW - Network energy effciency

KW - Superlinear polynomial cost

UR - http://www.scopus.com/inward/record.url?scp=85018371419&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-55911-7_41

DO - 10.1007/978-3-319-55911-7_41

M3 - Conference contribution

AN - SCOPUS:85018371419

SN - 9783319559100

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 571

EP - 585

BT - Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings

A2 - Jager, Gerhard

A2 - Steila, Silvia

A2 - Gopal, T.V.

PB - Springer Verlag

T2 - 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017

Y2 - 20 April 2017 through 22 April 2017

ER -

Shi Y, Zhang F, Liu Z. Hardness of routing for minimizing superlinear polynomial cost in directed graphs. 在 Jager G, Steila S, Gopal TV, 编辑, Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings. Springer Verlag. 2017. 页码 571-585. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-55911-7_41

Hardness of routing for minimizing superlinear polynomial cost in directed graphs

摘要

出版系列

会议

联合国可持续发展目标

访问文件

其它文件与链接

指纹

引用此