Personal tools

Approximation Algorithms for Broadcast Scheduling.

— filed under:

Dr. Rajiv Ghandi, University of Maryland

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

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.

« April 2018 »
Upcoming Events
Math/CS Club
Wed, Apr 25, 2018
The Mathematical Match Game Brody Johnson, SLU
PhD Oral Defense
Thu, Apr 26, 2018
Finite, fiber-preserving group actions on orientable Seifert manifolds Benjamin Peet, SLU
PhD Oral Exam
Fri, Apr 27, 2018
Leavitt Path Superalgebras Katie Radler, SLU
Annual Awards Ceremony
Fri, Apr 27, 2018
The 2018 Math & Statistics Department Award Ceremony Featuring Sarah Greenwald, Appalachian State University
Geometry/ Topology Seminar
Tue, May 01, 2018
Necessary and Sufficient Conditions for a Triangle Comparison Theorem, II James Hebda, SLU
Previous events…
Upcoming events…