演讲人： Pekka Orponen 芬兰阿尔托大学
时间： 2011-10-24 11:00-2011-10-24 12:00
地点：FIT 1-222
课件下载：点击下载
内容：
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.)
个人简介:
