|
|
|
| |
|
|
| |
 |
 |
|
INFORMS Journal on Computing |
|
|
| |
|
|
| | Volume Number 20 Issue Number 1 First Page 3 Last Page 20 Cover Date February 01, 2008
|
|
| |
|
|
| |
|
|
| |
Monitoring an Information Source Under a Politeness Constraint
Jonathan Eckstein, Avigdor Gal, Sarit Reiner |
|
| |
We describe scheduling algorithms for monitoring a single information source whose contents change at times modeled by a nonhomogeneous Poisson process. In a given time period of length T, we enforce a server-side politeness constraint that we may only probe the source at most n times. This constraint, along with an optional constraint that no two probes may be spaced less than delta time units apart, is intended to prevent the monitor from being classified as a nuisance to be ``locked out'' of the information source. To develop our algorithms, we use a portion of the cost model developed in our earlier work. Our first algorithm assumes a discrete set of N > n possible update times, and uses dynamic programming to identify a provably optimal subset of n of these times at which to probe the server. Our second algorithm is a simple direct search for locally improving any continuous-time schedule with respect to the same cost model. In particular, this improvement procedure may be applied to the schedule obtained from our first algorithm. We evaluate our algorithms using real-world data feeds. |
|
| |
 |
|
|
|
|
|
