.png){kind=icon}
返回
An LP-based heuristic algorithm for the node capacitated in-tree packing problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2011.05.019.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard. We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem. We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods. (C) 2011 Elsevier Ltd. All rights reserved.
Keyword:
Wireless ad hoc network
Sensor network
LP relaxation
Column generation
Relaxation heuristics
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
Viscoelastic properties of transformed cells: Role in tumor cell progression and metastasis formation.png)
Biorheology
BiorheologyIF0
PREAI
分享收藏An application-specific protocol architecture for wireless microsensor networks无线微传感器网络专用协议体系结构
PREAI
分享收藏Effect of Common Culinary Methods Practiced in Sri Lanka on the Nutrient Composition of Commonly Consumed Vegetables and Other Foods斯里兰卡常用烹饪方法对常见食用蔬菜及其他食品营养成分的影响
OAAI
OAAI分享收藏
查看更多内容