抖音网红黑料

Data Aggregation in Communication Networks

Release time:2011-10-24

Speaker: Pekka Orponen Aalto University, Finland

Time: 2011-10-24 11:00-2011-10-24 12:00

Venue: FIT 1-222

Download: Click!

Abstract:

In the problem of data aggregation in communication networks, messages arriving in the nodes of a network are to be forwarded to its root, and messages accumulated at a given intermediate node may be aggregated and forwarded together paying only a single link cost. However, messages accrue a delay penalty for waiting at a node, and the goal is to minimize the sum total of the link costs and delay penalties for a given message sequence. In an online setting, we obtain an O(log C_mst)-competitive algorithm for networks of bounded treewidth, where C_mst is the cost of the a minimum spanning tree in the network. The result is based on a relation between the data aggregation problem and the Prize-Collecting Steiner Tree problem, and it extends to any other networks where the PCST problem can be solved efficiently or admits a fully polynomial-time approximation scheme. (Joint work with Lauri Ahlroth and André Schumacher.)

Short Bio:

RETURN
演讲人 <a href='//users.ics.tkk.fi/orponen/' target='_blank'>Pekka Orponen</a> Aalto University, Finland 时间 2011-10-24 11:00-2011-10-24 12:00
地点 EN
TOP