Scheduling TV recordings for a recommender-based DVR

In a recommender-based digital video recorder, TV programs are considered for automatic recording on a hard disk. The choice of which programs to record depends on (i) the scores assigned to the programs by the recommender, (ii) the times and channels at which the programs are broadcast, and (iii) the number of tuners available for recording. For a given set S of n programs that are broadcast in a given time interval, and a given number m of tuners, we consider the problem of determining a subset S´ ⊆ S of programs with a maximum sum of scores that can be recorded with the m tuners. We show that this problem can be formulated as a min-cost flow problem and can be solved to optimality in O(mn²) time. In addition, we indicate how the min-cost flow approach can be adapted to take into account practical considerations such as uncertainties in the actual broadcast times of programs and programs that are broadcast multiple times in the given time interval. We present experimental results that suggest that, for realistic settings, near-optimal subsets can be determined on low-cost hardware.