Personal tools
 

Approximation Algorithms for Broadcast Scheduling.

— filed under:

Dr. Rajiv Ghandi, University of Maryland

What
  • Computer Science Seminar
When Fri, Feb 07, 2003
from 04:10 PM to 05:00 PM
Where RH 316
Add event to calendar vCal
iCal

Abstract: We will study a problem that arises in pull-based data dissemination systems, where information requested by clients is delivered via a broadcast channel. Client requests arrive over time. Broadcasting can exploit overlap among the client requests to reduce load. Thus, if multiple clients make a request for the same data then the server can satisfy the requests in one broadcast. We consider the broadcast scheduling problem in which the client requests at different times are known in advance and our goal is to schedule the broadcasts so as to minimize the total response time. This problem is NP-hard. We present approximation algorithms for this problem. We also describe general paradigms underlying our work and discuss the broader applicability of the techniques.

« February 2018 »
February
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
25262728
Upcoming Events
Colloquium
Fri, Mar 09, 2018
Higher Cluster Categories and Physics Gregg Musiker, University of Minnesota
Colloquium
Wed, Apr 18, 2018
Quantitative Topology? by Shmuel Weinberger, U Chicago
Previous events…
Upcoming events…