Loading...
Please wait, while we are loading the content...
Similar Documents
Online Scheduling Intervals and t-Intervals
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bachmann, Unnar Th. Halldórsson, Magnús M. Shachnai, Hadas |
| Copyright Year | 2010 |
| Abstract | A t-interval is a union of at most t half-open intervals on the real line. The special case where t = 1 is an interval. Often, the requests for contiguous allocation of a linear resource can be modeled by a sequence of t-intervals. We consider the problems of online scheduling intervals and t-intervals, which show up in Video-on-Demand services, high speed networks and molecular biology, among others. We derive lower bounds and (almost) matching upper bounds on the competitive ratios of randomized algorithms for scheduling intervals, 2-intervals and t-intervals, for any t > 2. While offline t-interval scheduling has been studied before, the online version is considered here for the first time. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.technion.ac.il/~hadas/PUB/online_tISP.pdf |
| Alternate Webpage(s) | http://www.researchgate.net/profile/Magnus_Halldorsson/publication/237231803_Online_Scheduling_Intervals_and_t-Intervals/links/5497ffda0cf2c5a7e3428169.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
