BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260916T191219Z
UID:Seminar-dept-333@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20131105T160000
DTEND:20131105T170000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Tomasz Radzik: New approximation bounds for some Maximum Network Lifetime problems\n\nWe consider the following Maximum Network Lifetime (MNL) problems, which may arise in the context of ad-hoc wireless networks. For a given (static) network N with known node-to-node communication costs, known initial capacities of node batteries, and a specified communication task, design a maximum number of communication rounds such that: (i) each round executes this specified communication task, and (ii) the initial capacities of the node batteries are sufficient to execute all rounds. The communication task can be, for example, gathering sensor data from the network in one specified node, and we would like to execute this task periodically, as many times as possible before the first node battery is depleted. We show improved approximation algorithms for the MNL problems for the three basic communication tasks - broadcast, convergecast (gathering of data) and unicast - and for "mixedcast" (a combination of the three). For example, we show a polynomial-time algorithm which computes 1/7-approximation solutions for the convergecast MNL problem, improving on the previous ratio of 1/31.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=333
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR