Optimally Selecting Partial Tv Programs
AssigneeKoninklijke Philips Electronics N.V.
InventorsWilhelmus Franciscus Johannes Verhaegh, Johannes Henricus Maria Korst
Life of this patent
Estimating the term…
Abstract
A system (600), apparatus (500), and method are provided to select a best set of TV programs for reception and recording by at least one tuner said TV programs being broadcast during a given time period [b, e] having a beginning time b and an ending time e. Partial and entire TV programs are considered and for each partial or entire TV program a user preference value is provided for its reception and recording. A minimum-cost network algorithm is used that solves the selection and viewing problem to optimality (guaranteed).
Claims19
A method for selecting a set of partial TV programs preferred by a viewer to be received in a given time period [b, e] beginning at time b and ending at time e, comprising the steps of:
- specifying a set S including a number N>1 preferred TV programs s each having a value function vs, begin time bs, an end time es;
- providing M≦1 tuners (503) to receive and record a partial TV program s of S;
- constructing a directed graph G=(V, E) comprising a set of nodes V and a set of edges E having associated costs and capacities, said nodes and edges being arranged in increasing time order from a start node at time 0 to a sink node at time ∞ and for each sεS including a node pair for at least one subpart of s and an edge between each included node pair, wherein for at least one program s the at least one subpart of s is not s;
- applying a minimum-cost network flow algorithm (502.1) to the directed graph G to determine an optimal subset S′ ⊂S such that the value function vs(l, r) over the subset S′ is maximized and the partial TV programs in S′ are received by the M≧1 tuners without conflicts during the time period [b, e].
An apparatus (500) for reception and delivery of viewer-preferred TV programs (504) during a given time period [b, e] beginning at time b and ending at time e, comprising:
- a memory module (501) containing a set S of a number n≧1 of viewer-preferred TV programs numbered s=1, . . . , n each having a begin time bs, an end time es, and a value function vs;
- a number m≧1 of tuners (503) to receive (and record) a TV program s of S;
- a processor module (502) configured to execute a partial program model formulation module to formulate and store in the memory (501) a partial program model of the set S and generate a directed graph G of partial TV programs therefrom, and a minimum-cost network algorithm module that accesses the memory to select a subset of the generated graph G of partial TV programs to receive and record, such that the selected subset of partial TV programs can be received by the plurality of tuners without conflicts within the time interval [b, e], and the total of the value function over the subset is maximized.
Dependencies are inferred from the claim text.