-

 

 

 




Optimization Online





 

Optimal Information Monitoring Under a Politeness Constraint

Jonathan Eckstein (jeckstei***at***rutcor.rutgers.edu)
Avigdor Gal (avigal***at***ie.technion.ac.il)
Sarit Reiner (reiner***at***techunix.technion.ac.il)

Abstract: We describe scheduling algorithms for monitoring an information source whose contents change at times modeled by a nonhomogeneous Poisson process. In a given time period of length T, we enforce a 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 procedure for locally improving any continuous-time schedule with respect to the same cost model. In particular, this improvment procedure may be applied to the schedule obtained from our first algorithm. We demonstrate the effectiveness of the algorithms by comparing them with previously-proposed methods, using real-world data feeds and varying preference parameters.

Keywords: Dynamic programming, information systems, global optimization, direct search, stochastic models

Category 1: Other Topics (Dynamic Programming )

Category 2: Applications -- OR and Management Sciences (Scheduling )

Category 3: Global Optimization (Applications )

Citation: RUTCOR Research Report RRR 16-2005 RUTCOR, Rutgers University 640 Bartholomew Road, Busch Campus Piscataway, NJ 08854 USA

Download: [Postscript]

Entry Submitted: 05/16/2005
Entry Accepted: 05/16/2005
Entry Last Modified: 05/16/2005

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society