(57)【要約】少なくとも１つのチューナによる受信及び記録のためにＴＶ番組の最良のセットを選択するシステム８００、装置７００及び方法が提供される。ＴＶ番組は、開始時間ｂと終了時間ｅを有する所与の時間［ｂ,ｅ］の間にチャネルのセットを通してブロードキャストされる。ＴＶ番組の一部及び全部が考慮され、それぞれＴＶ番組の一部又は全部について、ユーザの好みの値は、その受信及び記録のために提供される。さらに、部分的なＴＶ番組が全体的に受信されるのを確実にするために、プレロール及びポストロールが含まれる。選択及び視聴問題を解決するが、必ずしも最適である必要がない最小コストのネットワークアルゴリズムが使用される。ＴＶ番組の一部の受信の前又は後に、ＴＶ番組の全体的な部分が受信されたことを保証するため、更なる時間が許容される。
2009516952.tif 000002
【特許請求の範囲】
【請求項１】
時間ｂで開始し、時間ｅで終了する所与の期間［ｂ,ｅ］において視聴者により好まれる部分的なＴＶ番組のセットを選択する方法であって、
プレロール及びポストロールの少なくとも１つを含むようにチャネルを通して受信される部分的なＴＶ番組の開始時間及び終了時間を変更するために、関連される早さの関数εc及び遅さの関数λcをそれぞれのチャネルが有する、チャネルｃのセットＣを提供するステップと、
提供されるチャネルｃを通して受信される値の関数νs、開示時間ｂs及び終了時間ｅsをそれぞれのＴＶ番組が有する、Ｎ≧１個の部分的なＴＶ番組ｓのセットＳを規定するステップと、
Ｍ≧１個のチューナを設けて、部分的なＴＶ番組ｓ∈Ｓを受信及び記録するステップと、
チャネルｃを通して受信されるそれぞれのＴＶ番組ｓについて前記開始時間及び終了時間に対応するノードのセットＶ、及び関連するコスト及びキャパシティを有するエッジのセットを含む有向グラフを構築するステップと、
最小コストのネットワークフローアルゴリズムを前記有向グラフに適用して、前記期間［ｂ,ｅ］の間にコンフリクトなしで、サブセットＳ’を通して前記値の関数νs（ｌ,ｒ）が最大にされ、前記サブセットＳ’における部分的なＴＶ番組がＭ≧１により受信されるように、前記サブセットＳ’⊆Ｓを決定するステップとを含み、
前記有向グラフは、
プレロールとポストロールとを含むように前記関連される早さの関数と遅さの関数によりそれぞれ変更される開始ノード及び終了ノードの中央のタイムラインと、
それぞれのチャネルｃについて、チャネルを通して受信されるそれぞれのＴＶ番組ｓについて前記開始ノード及び前記終了ノードのチャネルｃのタイムラインと、
予め決定されたルールに従ってチャネルｃの少なくとも１つのタイムラインの対応するノードをもつ前記中央のタイムラインのそれぞれのノードと、
を接続することを特徴とする方法。
【請求項２】
特定のチャネルｃ∈Ｃで受信されたセットＳの部分的なＴＶ番組のそれぞれは、同じチャネルｃの他のＴＶ番組と時間的にオーバラップしない、
請求項１記載の方法。
【請求項３】
前記適用するステップは、値の関数がサブセットＳ’を通して値の関数νsの線形総和を計算するステップを更に含む、
請求項１記載の方法。
【請求項４】
前記規定するステップは、視聴者又はリコメンダが前記セットＳを規定するステップを更に含む、
請求項１記載の方法。
【請求項５】
前記値の関数は、表示を早く終了し、表示を遅く開始する予め決定されたペナルティを有する線形関数である、
請求項１記載の方法。
【請求項６】
前記構築するステップは、
時間０でのソースノードから、それぞれＴＶ番組ｓ∈Ｓの変更された開始時間ｂs及び終了時間ｅsを通して、時間∞でのシンクノードに増加する順序で、前記中央のタイムラインのノード及びエッジを配置するステップと、
それぞれのチャネルｃについて、チャネルｃを通して受信されたそれぞれのＴＶ番組ｓの開始時間及び終了時間を通して、増加する順序でチャネルｃのタイムラインのノード及びエッジを配置するステップと、
を更に含む請求項１記載の方法。
【請求項７】
前記中央のタイムラインのそれぞれのエッジは、キャパシティＭ≧１及びコスト０を有し、
それぞれのチャネルのタイムラインのそれぞれのエッジは、キャパシティ１及び第一のプリセット関数に従って決定されたコストを有し、前記時間ポイントの第二のノードのペアは、その時間からＴＶ番組ｓ∈Ｓのコンテンツがチャネルｃを通して受信され、その時間までＴＶ番組ｓ∈Ｓのコンテンツがチャネルｃを通して受信される時間であり、
前記中央のタイムラインと少なくとも１つのチャネルのタイムラインを接続するそれぞれのエッジは、キャパシティ１を有し、前記少なくとも１つのチャネルタイムラインの対応する時間ポイントｂsとｅsに前記早さの関数と前記遅さの関数によりそれぞれ変更される前記中央のタイムラインのノードｂsとそれぞれのノードｅsとを接続し、前記エッジは、第二の予め設定された関数に従って決定されるコストを有する、
請求項６記載の方法。
【請求項８】
前記適用するステップは、前記値の関数が前記サブセットＳ’を通してνsの線形総和を計算するステップを更に含む、
請求項７記載の方法。
【請求項９】
前記規定するステップは、前記視聴者又はリコメンダが前記セットＳを規定するステップを更に含む、
請求項８記載の方法。
【請求項１０】
前記値の関数は、表示を早く終了し、表示を遅く開始する予め決定されたペナルティを有する凸関数である、
請求項９記載の方法。
【請求項１１】
時間ｂで開始し、時間ｅで終了する所与の期間［ｂ,ｅ］の間に視聴者により好まれるＴＶ番組の受信及び送出の装置であって、
開始時間ｂs、終了時間ｅs及び値の関数νsをそれぞれのＴＶ番組が有する、ｓ＝１,…,ｎで番号付けされる視聴者により好まれるＮ≧１のＴＶ番組のセットＳを含むメモリモジュールと、
前記ＴＶ番組ｓのセットＳを受信（及び記録）するＭ≧１のチューナと、
前記セットＳの部分的な番組モデルを定式化して前記メモリに記憶し、プレロール及びポストロールを有する部分的なＴＶ番組の有向グラフＧを生成する部分的な番組モデル定式化モジュールを実行し、前記メモリにアクセスして受信及び記録すべき部分的なＴＶ番組の生成されたグラフＧのサブセットを選択する最小コストネットワークアルゴリズムモジュールを実行するプロセッサモジュールとを有し、
部分的なＴＶ番組の選択されたサブセットは、前記期間［ｂ,ｅ］でのコンフリクトなしで、複数のチューナにより受信され、前記サブセットを通して値の関数は最大となる、
ことを特徴とする装置。
【請求項１２】
視聴者により好まれる部分的なＴＶ番組のＴＶ視聴のセッションをスケジュールするシステムであって、
ＴＶ番組を視聴するＴＶセットと、
視聴者に好まれるＴＶ番組を選択及び受信し、開始時間ｂと終了時間ｅを有する予め決定された時間間隔［ｂ,ｅ］の間に受信されたＴＶ番組の少なくとも１部を前記ＴＶで表示する、請求項１１記載の装置と、
を有することを特徴とするシステム。
【請求項１３】
時間ｂで開始し、時間ｅで終了する所与の期間［ｂ,ｅ］の間に視聴者により好まれるＴＶ番組の受信及び送出の装置であって、
開始時間ｂs、終了時間ｅs及び値の関数νsをそれぞれのＴＶ番組が有する、視聴者により好まれるＮ≧１のＴＶ番組ｓのセットＳを記述するデータを含むメモリモジュールと、
前記ＴＶ番組ｓのセットＳを受信及び記録するＭ≧１のチューナのセットと、
前記メモリモジュールに含まれるセットＳを記述するデータと前記チューナのセットとを使用して、請求項１記載の方法を実行するプロセッサモジュールと、
を有することを特徴とする装置。
【請求項１４】
時間ｂで開始し、時間ｅで終了する所与の期間［ｂ,ｅ］の間に視聴者により好まれる部分的なＴＶ番組の受信及び送出の装置であって、
開始時間ｂs、終了時間ｅs及び値の関数νsをそれぞれのＴＶ番組が有する、視聴者により好まれるＮ≧１のＴＶ番組ｓのセットＳを記述するデータを含むメモリモジュールと、
前記部分的なＴＶ番組ｓのセットＳを受信（及び記録）するＭ≧１のチューナのセットと、
前記メモリモジュールに含まれるセットＳを記述するデータと前記チューナのセットとを使用して、請求項４記載の方法を実行するプロセッサモジュールと、
を有することを特徴とする装置。
【請求項１５】
視聴者により好まれる部分的な番組のＴＶ視聴セッションをスケジュールするシステムであって、
ＴＶ番組を視聴するＴＶセットと、
視聴者に好まれる部分的なＴＶ番組を選択及び受信し、開始時間ｂと終了時間ｅを有する予め決定された時間間隔［ｂ,ｅ］の間に受信されたＴＶ番組の少なくとも１部を前記ＴＶで表示する、請求項１１記載の装置と、
を有することを特徴とするシステム。
【請求項１６】
視聴者により好まれる部分的な番組のＴＶ視聴セッションをスケジュールするシステムであって、
ＴＶ番組を視聴するＴＶセットと、
視聴者に好まれる部分的なＴＶ番組を選択及び受信し、開始時間ｂと終了時間ｅを有する予め決定された時間間隔［ｂ,ｅ］の間に受信されたＴＶ番組の少なくとも１部を前記ＴＶで表示する、請求項１３記載の装置と、
を有することを特徴とするシステム。
【請求項１７】
メモリに記憶されるコンピュータプログラムであって、
請求項１記載の方法を実行する実行可能なモジュールと、請求項２記載の方法への入力として、チャネルのセットＣ及びＴＶ番組のセットＳを含むデータモジュールとを有し、前記セットＳは、開始時間ｂs、終了時間ｅs及び値の関数νsをそれぞれのＴＶ番組が有するｎ≧１の好ましい部分的なＴＶ番組ｓを含む、
ことを特徴とするコンピュータプログラム。
【請求項１８】
メモリに記憶されるコンピュータプログラムであって、
請求項３記載の方法を実行する実行可能なモジュールと、請求項３記載の方法への入力として、チャネルのセットＣ及びＴＶ番組のセットＳを含むデータモジュールとを有し、前記セットＳは、開始時間ｂs、終了時間ｅs及び値の関数νsをそれぞれのＴＶ番組が有するｎ≧１の好ましい部分的なＴＶ番組ｓを含む、
ことを特徴とするコンピュータプログラム。
【請求項１９】
メモリに記憶されるコンピュータプログラムであって、
請求項９記載の方法を実行する実行可能なモジュールと、請求項４記載の方法への入力として、チャネルのセットＣ及びＴＶ番組のセットＳを含むデータモジュールとを有し、前記セットＳは、開始時間ｂs、終了時間ｅs及び値の関数νsをそれぞれのＴＶ番組が有するｎ≧１の好ましい部分的なＴＶ番組ｓを含む、
ことを特徴とするコンピュータプログラム。
【請求項２０】
メモリに記憶されるコンピュータプログラムであって、
請求項９記載の方法を実行する実行可能なモジュールと、請求項５記載の方法への入力として、チャネルのセットＣ及びＴＶ番組のセットＳを含むデータモジュールとを有し、前記セットＳは、開始時間ｂs、終了時間ｅs及び値の関数νsをそれぞれのＴＶ番組が有するｎ≧１の好ましい部分的なＴＶ番組ｓを含む、
ことを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、タイムマージンを使用して、所与のタイムインターバルの間に制限された数のチューナを使用して記録されるべき部分的なテレビ番組の（ほぼ）最適な選択を行い、第一の番組を記録した後の別のＴＶチャネルへのスイッチングと、前の状況におけるタイムマージンを強制することで同じチャネルに同調されて留まることとの間で区別するシステム、装置及び方法に関する。ＴＶ番組の一部又は全部としてパートが定義される。
【背景技術】
【０００２】
パーソナルビデオレコーダ（ＰＶＲＳ）は、ハードディスク又はＤＶＤの何れかで、ＴＶ番組を記録するために利用可能である。これらＰＶＲをプログラムすることは、記録されるべきＴＶ番組でシンプルにクリックすることで、電子番組ガイド（ＥＰＧ）を使用して通常は達成される。さらに、到来するＴＶ番組について、どの位多くの視聴者がその番組を好むかを予測するリコメンダが利用可能な場合がある。
【０００３】
地上波、衛星又はケーブルコネクションを介して益々増加する利用可能なテレビ番組により、視聴又は記録するＴＶ番組を選択する視聴者のタスクは、急速に多くなり、手動で対処することができない。デジタルテレビジョンの出現により、チャネル数、したがって選択すべきオプション数も多くなっている。したがって、視聴者は、全ての利用可能なプログラミングコンテンツを概観することがもはやできず、視聴者が関心のあるＴＶ番組を逸する可能性がある。
【０００４】
それぞれの週で利用可能な多数のＴＶ番組のため、印刷されたＴＶプログラムガイドは、厄介であり、電子番組ガイド（ＥＰＧ）は、この問題に対するソリューションとして開発されている。ＥＰＧは、ＴＶスクリーンで多数のチャネルについて利用可能なＴＶ番組を与える。しかし、制限された数のＴＶ番組のみをＴＶスクリーンに一度に表示することができ、すなわちチャネル数及びスクリーンで表示される部分の時間インターバルの長さは、非常に制限されている。これは、この類のテクスチャ情報の表示のためにＴＶスクリーンの乏しい解像度から生じる。また、解像度が十分に高い場合でさえ、非常に多数の利用可能なＴＶコンテンツから選択するタスクは、平均的な視聴者を苦しめる。
【０００５】
どの部分的なＴＶ番組を選択すべきか、何時どのように様々なＴＶチャネルの中から視聴時間を配置すべきかといった視聴者の問題、すなわち、選択された部分的なＴＶ番組が完全に受信されることを保証する視聴者に特化した視聴スケジュールを開発する問題を改善するため、ＥＰＧは、キーワードによりサーチ（フィルタリング）するオプションを提供するが、選択間の時間が番組の受信を完了するのを許容しない。このように、ＥＰＧは、視聴者によりスクリーンされ、選択されるべきＴＶ番組の数を管理可能な数に低減することができるが、チャネルを切り換えることで生じる部分的なＴＶ番組の終了の欠如に対処することができない。複数の視聴者にとって関心のないＴＶ番組を視聴者が間引きする別の方法は、人工知能（ＡＩ）技術に基づいたリコメンダシステムの使用によるが、同じ終了の問題の欠如が存在する。これらＡＩリコメンダシステムは、視聴者が何を好きで何が嫌いであるかを示す視聴者の好みのプロファイルを保持し、このプロファイルを使用して、どの程度にまで視聴者が新たに提供されたＴＶ番組を好きであるかに関してそれぞれの新たに提供されたＴＶ番組をスコア付けする。次いで、予め決定された視聴者に特化した許容値を超えてスコア付けされたＴＶ番組は、ＥＰＧにおいてハイライト表示されるか、視聴者には、これらＴＶ番組のリストが提供される。しかし、これらのソリューションによる問題は、ＴＶ番組が時間的にオーバラップするか否かを考慮していないことであり、したがって、視聴者は、依然として、受信すべき上位にスコアリングされたＴＶ番組の視聴者に特化したスケジュールを編集し、選択された部分の受信の終了についてそれらの間で十分な時間を許容しなければならない。言い換えれば、フィルタ及びリコメンダは個々のＴＶ番組のリストを供給するので、かかるリストは、視聴するＴＶ番組のスケジュールを作成する視聴者の問題に対して不完全なソリューションであり、特に、チャネルがその受信間で切り換えられるときに終了を許容するために選択される部分的なＴＶ番組の間で十分な時間を残す方法がない。同様の状況は、ＴＶ番組の記録について存在する。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
チャネルが切り換えられる必要があるときに終了の時間を許容する所与の時間インターバルであって、選択された部分的なＴＶ番組を受信／記録するために利用可能な有限数Ｍ≧１のチューナのみを視聴者が有するときに予め決定された視聴者の好みを最大にする所与の時間インターバルについて、部分的なＴＶ番組の効率的な選択のためのソリューションが必要とされる。
【課題を解決するための手段】
【０００７】
本発明のシステム、装置及び方法は、連続する部分的なＴＶ番組の間でチャネルが切り換えられる時間マージンを含み、制限された数のチューナをもつ、部分的なＴＶ番組の（実質的に）最適な選択を行うことが保証される有効なアルゴリズムを提供する。すなわち、選択は、完全な受信を保証しつつ、選択された部分的なＴＶ番組と関連付けされた視聴者の好みの値の合計を実質的に最大にする。これらの好みは、たとえば本発明を使用して（実質的に）最適な選択が行われる前に、利用可能な部分的なＴＶ番組の最初のフィルタリングを提供するリコメンダにとって既知であることが想定される。
【０００８】
視聴者が部分的なＴＶ番組を選択するのを望む時間インターバルが与えられると、このインターバルに含まれる全ての部分的なＴＶ番組は、最初に集められ、それぞれ収集された部分的なＴＶ番組の値の関数が取得される。第二に、それぞれの部分的なＴＶ番組の開始及び終了時間のポイントは、方向付けされたグラフＧのノードとして決定され、セットＳは、所与の時間インターバル内の開始及び終了時間ポイントのうちの少なくとも１つを有する部分的なＴＶ番組について決定される。第三に、時間０のソース及び時間∞のシンクノードが形成され、Ｇのグラフは、ソースから、Ｇの時間的に順序付けされたノードを通してシンクまで描かれ、すなわち、中央のタイムライン又はエッジのチェインは、ソースノードからＧのそれぞれ連続する時間的に順序付けされたノードを通して形成され、それぞれのエッジは、“０”のコスト及びＭのキャパシティを有しており、Ｍ≧１は、ＴＶ番組を受信するために利用可能なチューナ数である。
【０００９】
つぎに、チャネルｃについて類似のタイムラインは、それぞれのチャネルｃでブロードキャストされたＳにおける部分的なＴＶ番組について構築され、既に受信されているＴＶチャネルと所与の時間で受信されていないチャネルとの間で区別される。すなわち、中央のタイムラインに既に含まれるノードに加えて、ＴＶチャネルｃでブロードキャストされるＳにおけるそれぞれのＴＶ番組は、開始及び終了ノードのペアにより表され、且つ中央のタイムラインではなくチャネルｃのタイムライン上でそれらの間でエッジを有するゼロ以上の部分的なＴＶ番組に更に分割される。これにより、それぞれのＴＶ番組は、その開始時間又は別のＴＶ番組の終了時間での受信を開始することができ、且つ、それぞれのＴＶ番組は、その終了時間又は別のＴＶ番組の開始時間での受信を終了することができる。それぞれの係る結果的に得られる部分的なＴＶ番組はＳに追加され、視聴者に特化した値の関数により決定される関連される視聴者の好みの値を有する。詳細な説明で以下に示されるように、最適さの損失は、この制約から生じない（以下の理論１を参照されたい）。
【００１０】
本発明における重要なことは、中央のタイムラインを含むグラフＧであり、このタイムラインから、このタイムラインまで、含まれる全体又は部分的なＴＶ番組のエッジが実行され、チャネルｃのタイムラインにおける、それぞれのＴＶチャネルｃについて、このエッジは、これらＴＶ番組の全体及び一部のネガティブな好みの値を表し、このＴＶ番組の全体及び一部は、セットＳに含まれる。
【００１１】
最後に、タイムマージンは、中央のタイムラインからあるチャネルのタイムラインにまで実行されるエッジの時間差として、このモデル、すなわちグラフに含まれ、このタイムマージンは、あるチャネルのタイムライン内のパラレルなエッジを除去し、そのチャネルのタイムラインにおける視聴者の好みの値を適切に表すために必要とされる。
【００１２】
この方向を持ったグラフＧが与えられると、最小のコストのネットワークアルゴリズムは、このグラフに適用され、所与の時間インターバルについて部分的なＴＶ番組Ｓ’のサブセットを決定し、ほぼ最大の視聴者の満足度を提供、すなわち部分的なＴＶ番組のセットＳ’について視聴者の好みの値の全体をほぼ最大にする。選択されたサブセットは、ほぼ最適となるように保証される、サブセットを選択するアルゴリズムは、多項式時間で実行することが保証される。
【発明を実施するための最良の形態】
【００１３】
本発明のシステム、装置及び方法は、視聴者にとって最適なＴＶの経験を決定するやり方を提供するものであって、この経験とは、少なくとも１つのチューナを使用して部分的な好適なＴＶ番組を視聴するのと同様に記録することを含む。
【００１４】
本発明のシステム、装置及び方法は、視聴者のＴＶ番組スケジューリングの問題に対する最適な解決策を得るための、数学的な式及び解決策を提供する。本発明のシステム、装置及び方法の範囲は、所与の時間でブロードキャストされている全ての利用可能なＴＶ番組について予め決定された視聴者の好みに基づいて、所与の数の利用可能なチューナによりどのＴＶ番組を視聴又は記録のために選択すべきか、という問題を含む。
【００１５】
簡略化された問題の設定がはじめに説明され、より複雑な問題の設定を解決するため、より多くのファクタを含み、簡略化された問題について開発されたアルゴリズムを詳述するために簡略化された問題設定の拡張が続く。
【００１６】
本発明のシステム、装置及び方法の好適な実施の形態では、幾つかの想定が最初に行われる。  
１．好みの値又はスコアは、複数の候補となるＴＶ番組のそれぞれについて提供され、どの位多くの視聴者が候補となるＴＶ番組を好むかを示す。
２．それぞれの好みのスコアは、視聴者により、又はリコメンダツールにより明示的に与えられる。
３．選択されている多数のＴＶ番組の全体の好みのスコアは、個々のＴＶ番組の提供された好みのスコアの線形和により与えられる。
４．視聴のために選択されたＴＶ番組は、ＴＶ番組がブロードキャストされた瞬間で視聴されることが想定され、ＴＶ番組が後に視聴される場合、そのブロードキャストの間に記録されることがシンプルに想定される。
【００１７】
それぞれの簡略化及び拡張は、問題を最小コストのネットワークフローの問題に変換する有向グラフとしてモデル化される。最小コストのネットワークフローの問題は、多項式時間で解決することができるので、対応するＴＶ番組の選択の問題は、有効に解決される。
【００１８】
第一のモデルは、１つのチューナを使用して完全なＴＶ番組を選択する。完全なＴＶ番組を選択する問題は、以下のように定義される。
【００１９】
定義１（プログラム選択問題（ＰＳＰ））。ＴＶ番組ｓのセットＳが与えられ、それぞれのＴＶ番組ｓについて、開始時間ｂsと終了時間ｅsも規定される。さらに、それぞれのＴＶ番組について、値ｖs＞０が与えられ、この値は、このＴＶ番組が（完全に）視聴される場合に全体の値を反映する。問題は、サブセットＳ’⊆Ｓを決定することであり、これにより、サブセットＳ’におけるＴＶ番組は、時間的に競合せず、すなわち全てのｓ，ｔ∈Ｓ’，ｓ≠ｔについてｂs＞ｅt  Ｖ  ｂt＞ｅsとなり、
（外１）
2009516952.tif 000003
により与えられるこのサブセットの全体の値は最大にされる。
【００２０】
ＴＶ番組の値ｖsは、視聴者により明示的に与えられるか、リコメンダを使用して推定される。ＴＶ番組ｓのリコメンダスコアｐsを好みの比重として考慮して、全体の値は、ｖs＝ｐs（ｅs−ｂs）により与えられる。所定の時間インターバルにおいて多数のＴＶ番組を通して全体の値を最大にすることは、平均の好みの比重を最大にすることに対応する。
【００２１】
ＴＶ番組の選択の問題は、以下のような最小コストのフロー問題として定式化される。ネットワークＧのノードのセットＶは、ソースノード及びシンクノード、並びにＴＶ番組のそれぞれの開始又は終了時間のノードにより与えられる。したがって、以下に示される。
【００２２】
【数１】
2009516952.tif 000004
ここでノード０はソースを表し、∞はシンクを表す。Ｖにおけるノード（すなわち時間）をｔ1,…,ｔnで示し、ｎ個の個別の時間は、増加する順序で配置される。ここで、全ての時間は、ソース時間ｔ1＝０よりも大きく、シンク時間ｔn＝∞よりも小さいことが想定される。
【００２３】
エッジのセットＥは、２つの部分から構成される。はじめに、定義により、ゼロコストを有する、全てのｉ＝１,...,ｎ−１についてノードエッジ（ｔi,ｔi+1）を含むソースからシンクへのタイムライン上にエッジが存在する。第二に、それぞれのＴＶ番組ｓ∈Ｓについて、コスト−ｖsによりエッジ（ｂs,ｅs）が追加される。全てのエッジは、キャパシティ１を有することが想定される。
【００２４】
グラフ構造の例について、１８：００ｈから２２：００ｈまでの時間インターバルにおいてＴＶ番組Ａ，Ｂ,…,Ｊをカバーする、図１に示されるＴＶ番組のセットを考える。時間ポイントの対応するセットＶは、Ｆ＝｛0,  18:00,  19:00,  19:30,  20:00,  20:30,  21:00,  22:00,  ∞｝により与えられ、エッジのセットは、図２に与えられるようなものである。
【００２５】
ここで、最大値をもつオーバラップしないサブセットを決定することは、最小のコストをもつソースからシンクへのＧにおける１つのフローを発見することに対応する。この最小のコストフローにおいて、ＴＶ番組に対応するエッジが１のフローを保持する場合、このＴＶ番組はＳ’に含まれ、さもなければＳ’に含まれない。したがって、問題は、最小コストのフローアルゴリズムにより解決される。言い換えれば、ＰＳＰは、効率的に解決される。
【００２６】
先の式におけるように、全てのキャパシティは１であり、最小コストのフロー問題は、（ソースからシンクへの）最短経路の問題に低減され、（ネガティブ）なコストは、エッジ長として使用される。
【００２７】
最小コストのフロー問題。有向グラフＧ＝（Ｖ,Ｅ）が与えられたとする。Ｅにおいてそれぞれのエッジｉｊと関連付けされるコストｃij及びキャパシティｕij＝１、ならびに、Ｖにおけるそれぞれのノードｖと関連付けされる需要（供給）ｂvが存在するものとする。問題は、それぞれのノードについて、供給／需要の制約
【００２８】
【数２】
2009516952.tif 000005
及びエッジの制約
【００２９】
【数３】
2009516952.tif 000006
を満たす最小コストのフローを発見することである。フローのコストは、以下のように定義される。
【００３０】
（外２）
2009516952.tif 000007
本発明では、定義により、それぞれのエッジのキャパシティは１である。さらに、ｂ1＝−１，ｂn＝１、及びｉ＝２,…,ｎ−１についてｂi＝０である。
【００３１】
多数のＴＶ番組は、１を超えるチューナが利用可能であり、さらに選択されたＴＶ番組が記録されるときは何時でもパラレルに受信される。また、問題は、２ステージのＴＶプログラミングアプローチに関連し、この場合、最初に、どのＴＶ番組を受信し、次いでＰＭ（Persistent  Memory）に記憶するかを決定し、次いで、ＰＭに記録されている全てのコンテンツからＴＶスケジュールを決定する。
【００３２】
定義２（マルチチューナ番組選択問題（ＭＰＳＰ））。ＴＶ番組のセットＳが与えられ、それぞれのＴＶ番組ｓについて、開始時間ｂs、終了時間ｅs、及び値ｖsが与えられる。さらに、予め決定された数Ｍのチューナも与えられる。問題は、サブセットＳ’⊆Ｓを決定することである。これにより、全ての時間で、多くともＭ個のＴＶ番組が選択され、すなわち全ての時間ｘについて、
【００３３】
【数４】
2009516952.tif 000008
であり、
（外３）
2009516952.tif 000009
により与えられるこのサブセットの全体の値が最大にされる。
【００３４】
ＭＰＳＰは、上述された等価なネットワークフローの変換を使用して、ＰＳＰと同様のやり方で解決される。ＭＰＳＰについて、エッジ（ｔi,ｔi+1）のキャパシティがＭに変化し、Ｍ個のチューナが利用可能であることを反映することが異なり、ある番組が多数買いにわたり受信されることが望まれないように、ＴＶ番組のエッジのキャパシティが１のままである。
【００３５】
つぎに、ソースからシンクへのＭの最小コストのフローが決定され、グラフにおける対応するエッジがこの発見された最小コストのフローのソリューションにおいて（１の）フローを保持するそれぞれのＴＶ番組は、Ｓ’に含まれる。
【００３６】
つぎに、完全なＴＶ番組の上述された単一のチューナのソリューションは、部分的にのみ幾つかのＴＶ番組を視聴することを含むために拡張される。このため、値関数ｖs（ｌ,ｒ）は、ｂs≦ｌ≦ｒ≦ｅsとして、部分的に開いたインターバル［ｌ,ｒ）の間に番組を視聴する値を示すそれぞれのＴＶ番組ｓについて導入される。この値の関数について、以下が想定される。
【００３７】
【数５】
2009516952.tif 000010
定義３（部分的な番組選択問題（ＰＰＳＰ））。ＴＶ番組のセットＳが与えられ、それぞれのＴＶ番組ｓについて、開始時間ｂsと終了時間ｅsが与えられる。さらに、それぞれのＴＶ番組について、値の関数ｖsが与えられる。問題は、それぞれのＴＶ番組ｓについて、
（外４）
2009516952.tif 000011
として、番組を視聴するインターバルの（おそらく空である）セットＩs＝｛［ｌ1,ｒ1），．．．,［ｌks,ｒks］｝を決定することであり、これにより、ＴＶ番組の選択されたインターバルは、時間的にコンフリクトしない。このことは、全てのｓ,ｔ∈Ｓ’，ｓ≠ｔ及び全ての［ｌ,ｒ）∈Ｉs，［ｌ’,ｒ’）∈Ｉtについて、ｌ≧ｒ’  ｖ  ｌ’≧ｒを有し、すなわち、ｓの任意のインターバルは、ｔの任意のインターバルよりも遅く、逆も然りであることを意味する。なお、半分の開いたインターバルを使用したので、１つのインターバルは、別のインターバルが終了するのと同じ瞬間で正確に開始することが可能である。目的は、
（外５）
2009516952.tif 000012
により与えられる選択されたインターバルの全体の値が最大にされることである。
【００３８】
値の関数は、大部分は任意の形式からなり、以下の説明では、値の関数を凸型にすることが制約され、次のセクションで説明される。より効率的に扱うことができる更に制限された形式は、ペナルティをもつ線形な値の関数であり、以下に説明される。
【００３９】
凸型（convenx）の値の関数。  
凸型の値の関数は、全てのα∈［０,１］について、以下の関係
【００４０】
【数６】
2009516952.tif 000013
が保持される条件を満たす値の関数ｖである。
【００４１】
大部分の実際の値の関数は、この条件を満たす。たとえば、凸型の値の関数は、
【００４２】
【数７】
2009516952.tif 000014
のような線形の関数であるか、又は
【００４３】
【数８】
2009516952.tif 000015
のような二次の関数である。
【００４４】
凸型の値の関数の１つの特性は、次の理論が述べるように、あるＴＶ番組から別の番組に切換わる可能性のあるポイントの数を低減できることである。
【００４５】
理論１。全てのＴＶ番組ｓ∈Ｓについて、ｖs（ｌ,ｒ）が凸型である場合、最適さの損失なしに、ＰＰＳＰは、全てのｓ∈Ｓ及び［ｌ,ｒ）∈Ｉsについて、
【００４６】
【数９】
2009516952.tif 000016
によるソリューションに制限される。
【００４７】
言い換えれば、ＴＶ番組は、その開始時間で又は別のＴＶ番組の終了時間でのみ受信が開始され、その終了時間で又は別のＴＶ番組の開始時間でのみ受信が終了される。
【００４８】
証明。式（１）を満たさないＴＶ番組ｓ∈Ｓのインターバル［ｌ,ｒ）∈Ｉsを考える。時間ｌの直前に、最大数のチューナが使用される必要があり、さもなければ１を下げて解を改善することができる。ＴＶ番組ｓの受信が時間ｌから前方へ生じるとき、時間ｌで受信されるのを停止するＴＶ番組ｔ∈Ｓが存在する必要があり、すなわちＩtは、ｒ’＝１によりインターバル［ｌ’,ｒ’）を含む。ｌは式（１）を満たさないため、ｒ’＜ｅである。２つの代替的なソリューションを考え、１つは、ｌ1＝１−εで置き換えられるｌ及びｒ1’＝ｒ’−ε＝ｌ1で置き換えられるｒ’をもち、１つは、ｌ2＝１＋εで置き換えられるｌ及びｒ2’＝ｒ’＋ε＝ｌ2で置き換えられるｒ’をもつ。オリジナルのソリューションに比較して、第一のソリューションのコストは、オリジナルソリューションの値とは量
【００４９】
【数１０】
2009516952.tif 000017
だけ異なり、第二のソリューションのコストは、量
【００５０】
【数１１】
2009516952.tif 000018
だけ異なる。
【００５１】
したがって、以下に従う。
【００５２】
【数１２】
2009516952.tif 000019
この場合、後段の不等号は、ｖs及びｖtの凸型の特性に基づいている。したがって、少なくとも１つの差Δ1及びΔ2は、負ではなく、すなわち、２つの代替的なソリューションのうちの少なくとも１つは、少なくともオリジナルのソリューションと同様に良好である。したがって、最適さの損失なしに、ｌ及びｒ’の何れかをそれらがｅt又はｒになるまで増加することができるか（後者のケースでは、インターバル［ｌ,ｒ］はＩsから除かれる）、又は、ｌ及びｒ’をそれらがｂs又はｌ’になるまで減少することができる（後者のケースでは、［ｌ’,ｒ’）はＩtから除かれる）。  
同様なやり方で、式（２）が最適さの損失なしに想定されることを証明できる。
【００５３】
理論１の結果として、値の関数が凸型であると仮定して、ＴＶ番組を部分的に視聴するのを開始及び停止する制限された数の時間ポイントを考慮することが必要である。これに基づいて、図２の最小コストのネットワークは、図３に示されるように拡張される。ＴＶ番組エッジのコストは、ＴＶ番組の対応する部分について値により決定される。拡張されたグラフにおける最適なフローは、ＰＰＳＰの最適なソリューションに対応する。かかるフローでは、番組当たり多数のエッジが使用され、多数のインターバルの間にＴＶ番組を受信することに対応する。たとえば、最適なフローは、拡張されたグラフにおいてエッジＩ1及びＩ7を通して実行され、ＴＶ番組Ｉは、１９：００〜１９：３０、及び２０：００〜２１：００で選択されていることを意味する。１のフローのみが存在するので、同じ時間インターバルは決して２度カバーされない。さらに、２つの連続する部分を選択することは、多くとも、結合された部分を選択するのと同様に良好である（たとえば、Ｉ5を選択することは、少なくとも、Ｉ1及びＩ2を選択することと同様に良好である）。
【００５４】
拡張されたグラフにおけるエッジ数はオリジナルのグラフにおけるよりも非常に多いが、多項式で境界付けされている。より正確には、ＴＶ番組当たりのエッジ数は、異なる時間ポイントの数において２次である。さらに、１つのみのチューナが存在するので、エッジの数は、それぞれのペアの時間ポイント間で最良の数に制限され、これによりエッジの全体の数がＯ（ｎ2）に制限される。
【００５５】
ペナルティをもつ線形の値の関数。  
この代替では、値の関数の式は、ＴＶ番組を早期に終了するか、又はＴＶ番組を後に開始するためにペナルティをもつ線形関数に更に制限される。更に正式に、式
【００５６】
【数１３】
2009516952.tif 000020
の値の関数を考え、
【００５７】
【数１４】
2009516952.tif 000021
は、ＴＶ番組ｓが早めに終了するか、送れて開始する場合にペナルティを与える関数である。なお、この値の関数は、式（３）の右手側における全ての３つの項が凸型である時（すなわちペナルティ関数が凹型であるとき）、想定に従い、凸型である。式（３）における値の関数が与えられると、図４に示される別の拡張された最小のコストネットワークを定義することができる。より正式には、このグラフは、以下のように構築される。
【００５８】
ノードのセットＶは、第一に、それぞれの時間ポイントｔ1，．．．，ｔnのノードを含む。つぎに、ｊ−ｉ＞１として、時間ポイントｂs＝ｔi及びｅs＝ｔjをもつそれぞれＴＶ番組について、余分のノードｔksは、それぞれの中間的な時間ポイント、すなわちそれぞれｋ＝ｉ＋１,…,ｊ−１について構築することができる。図４において、“１９：００Ａ”でラベル付けされたノードは、中間的な時間ポイントについて係るノードの例である。
【００５９】
全てキャパシティ１をもつエッジのセットは、以下のように定義される。はじめに、コストゼロをもつ前のように、全てのｉ＝１,…,ｎ−１についてエッジ（ｔi,ｔi+1）が存在する。第二に、時間ポイントｂs＝ｔi及びｅs＝ｔjをもつそれぞれのＴＶ番組ｓ∈Ｓを考え、以下のように２つのケースを区別する。
・ｊ−ｉ＝１の場合、コスト−ｖsをもつエッジ（ｂs,ｅs）を追加する。
・ｊ−ｉ＞１の場合、多数のエッジを追加する。
【００６０】
【数１５】
2009516952.tif 000022
ここで、ペナルティをもつ線形の値の関数によるＰＰＳＰは、このグラフにおけるソースからシンクへの１つの最小のコストフローを発見することに対応する。さらに、ＴＶ番組当たりの多数の部分は、図３のグラフによるように選択される場合がある。
【００６１】
グラフにおけるフローと部分的なＴＶ番組との間の対応について、図４における例を更に考慮されたい。ＴＶ番組Ａは、エッジ（１８：００,１９：００Ａ）及びエッジ（１９：００Ａ,１９：３０）の両者が１のフローを形成する場合に完全に選択される。この状況は、エッジ（１９：００,１９：００Ａ）及び（１９：００Ａ,１９：００）は、フローを形成しない。これら先の２つのエッジを通したフローのコストは、ＴＶ番組Ａの選択の値ｖAに対応する−ｖAを正確に合計する。Ａの第一の部分のみを選択することは、エッジ（１８：００,１９：００Ａ）及び（１９：００Ａ,１９：００）を通して１のフローに対応し、結果的に、コスト−２ｖA／３＋ｃAfe、すなわちこの第一の部分について値２ｖA／３及びＡを早期に終了するペナルティｃAfeとなる。Ａの第二の部分のみを選択することは、エッジ（１９：００,１９：００Ａ）及び（１９：００Ａ,１９：３０）を通して１のフローに対応し、結果的に、コスト−ｖA／３＋ｃAsl、すなわちこの第二の部分について値ｖA／３及びＡを後に開始するペナルティｃAslとなる。
【００６２】
全体のノード数はＯ（|Ｓ|ｎ）であり、エッジの数は
【００６３】
【数１６】
2009516952.tif 000023
であるので、拡張されたグラフにおけるノード及びエッジの数は、この例のサイズにおいて多項式で境界付けされている。
【００６４】
ＰＳＰの次の拡張は、次の定義により与えられるように、部分的なＴＶ番組と同様に多数のチューナを可能にすることである。
【００６５】
定義４（マルチチューナの部分的な番組選択問題（ＭＰＰＳＰ））。ＴＶ番組のセットＳが与えられ、それぞれの番組ｓについて、開始時間ｂsと終了時間ｅsが与えられる。さらに、それぞれの番組ｓについて、値の関数ｖsが与えられ、チューナの数ｍが与えられる。問題は、それぞれのＴＶ番組ｓ∈Ｓについて、ｂs≦ｌ1＜ｒ1＜ｌ2＜ｒ2＜・・・＜ｌks＜ｒks≦ｅsにより、番組を視聴又は記録するインターバルの（おそらく空の）セットＩs＝｛［ｌ1,ｒ1）,…,［ｌks,ｒks）］を決定することであり、これにより、ＴＶ番組は、ｍ個のチューナをもつ選択されたインターバルで受信され、すなわち全ての時間ｘについて、
【００６６】
【数１７】
2009516952.tif 000024
であり、
（外６）
2009516952.tif 000025
により与えられる選択されたインターバルの全体の値が最大にされる。
【００６７】
残念なことに、上述されたような、調整されたキャパシティをもつ凸型の値の関数の拡張されたグラフを直接に利用することは機能しない。この理由は、その拡張されたグラフでは、パラレルに受信される同じＴＶ番組の幾つかの部分を選択する場合があることによる。たとえば、３つのチューナによる図３の例について、結果的に得られるソリューションは、ＴＶ番組Ｉ及び部分的なＴＶ番組Ｉ1及びＩ5を受信することであり、１９：００〜１９：３０のＴＶ番組の部分が３回受信されることを意味する。
【００６８】
ペナルティをもつ線形の値の関数について、図４で示されるグラフが適用される。変更は、１からｍへのエッジ（ｔi,ｔi+1）のキャパシティを増加する必要があることであり、ソースからシンクへのｍの最小コストフローが発見される必要がある。このグラフを再使用することができる理由は、それぞれのＴＶ番組及びそれぞれのインターバルについて、それをカバーする多くとも１つのエッジが存在し、したがって一度を超えて部分が受信されないためである。
【００６９】
図７を参照して、それぞれが開始時間ｂs及び終了時間ｅs、並びに視聴者又はリコメンダにより提供される視聴者の好みの関数νsを有する、Ｎ≧１のＴＶ番組ｓの所与のセットを記憶するメモリモジュール７０１からセットＳ（７０１．１）を選択するための装置７００が示されている。１つのチューナについて、値の関数は、ペナルティをもつ凸型の関数及び線形の関数から構成されるグループから選択される。装置は、プロセッサモジュールを更に有し、このモジュールは、Ｍ≧１のチューナにより受信され、おそらく記録される部分的なＴＶ番組を含む最適なセットＳ’⊆Ｓを選択するための最小コストのネットワークアルゴリズムモジュールを実行するか、それ自身が更に有している。
【００７０】
好適な実施の形態は、プレロール及びポストロールを含む。番組の開始時間と終了時間には、ある不正確さが存在する場合がある。したがって、番組が受信のために選択されている場合、番組を完全に受信するため、チューナは、時間εc（ｂs）≦ｂsから時間λc（ｅs）≧ｅsまで対応するチャネルに同調される必要がある。ここで、εc（ｔ）は、時間ｔから前方にスケジュールされるコンテンツを受信するため、どの位早くからチャネルｃに同調すべきかを示す関数であり、λc（ｔ）は、時間ｔまでスケジュールされるコンテンツを受信するため、どの位遅くまでチャネルｃに同調すべきかを示す。Εc及びλcの両者は、厳密に増加するものと想定される。
【００７１】
量ｂs−εc（ｂs）は、番組ｓのプレロールと呼ばれ、量λc（ｅs）＝ｅsは、番組ｓのポストロールと呼ばれる。番組選択問題への番組のプレロールとポストロールの主要な影響は、２つの連続する番組が同じチューナで受信され、これらの番組が異なるチャネルにある場合、番組が完全に受信される必要がある場合に第一の番組のスケジュールされた終了時間ｅsと第二の番組のスケジュールされた開始時間ｂsとの間にある時間が存在する。同じチェネルの２つの連続する番組について、かかる問題は存在しない。
【００７２】
チャネルｃの番組ｓの完全な値を得るために長いインターバルが必要とされる事実を反映するため、式（３）で与えられる値の関数は、以下のように再び定義される。
【００７３】
【数１８】
2009516952.tif 000026
この場合、ペナルティ関数は、以下のように再び定義される。
【００７４】
【数１９】
2009516952.tif 000027
代替的に、ペナルティ関数は、以下のように再び定義される。
【００７５】
【数２０】
2009516952.tif 000028
これら後者のペナルティ関数は、ペナルティが小さくなると、より多くの時間が終了ポイントを超えて含まれることを反映する。これらペナルティ関数は、凸型であり、式（４）の再び定義された値の関数はなお凸型である。したがって、理論１が適用され、番組の受信を開始又は停止する開始ポイントεc（ｂs）及び終了ポイントλc（ｅs）が考慮される。
【００７６】
定義５（プレロール及びポストロールによる番組選択問題（ＰＳＰＲ））。チャネルのセットＣが与えられると、それぞれのチャネルｃについて、早めの関数εc及び遅めの関数λcをもつ。さらに、ＴＶ番組のセットＳが与えられると、それぞれの番組ｓについて、開始時間ｂs及び終了時間ｅs、並びに式（４）により与えられる（再び定義された）値の関数ｖsをもつ。最終的に、チューナの数Ｍ≧１が与えられる。
【００７７】
問題は、それぞれの番組ｓ∈Ｓについて、εcs（ｂs）≦ｌ1＜ｒ1＜ｌ2＜ｒ2＜…＜ｌks＜ｒks≦λcs（ｅs）として、番組を視聴又は記録するインターバルの（おそらく空である）セットＩs＝｛［ｌ1,ｒ1）,…,［ｌks,ｒks］］を決定することである。これにより、Ｍを超えるチャネルを同時に同調する必要がなく、すなわち全ての時間ｘについて、
【００７８】
【数２１】
2009516952.tif 000029
であり、且つ、
（外７）
2009516952.tif 000030
により与えられる選択されたインターバルの全体の値が最大にされる。
【００７９】
ＰＳＰＲについて、特定のチャネルのＴＶ番組が時間的にオーバラップしないことが想定され、すなわち全てのｓ，ｔ∈Ｓ、ｓ≠ｔ、ｃs＝ｃtについて、［ｂs,ｅs］∩［ｂt,ｅt］＝Οである。なお、同じチューナで受信されている間、２つの係るＴＶ番組の選択されたインターバルはオーバラップする場合がある。たとえば、図１の例について、５分のプレロール及びポストロールを想定して、番組Ａ及びＢは同じチャネルであるため、インターバル［１７：５５,１９：３５）は、番組Ａについて選択され、インターバル［１９：２５，２０：０５）は、番組Ｂについて選択される。
【００８０】
これを最小コストのフロー問題であると考慮すると、プレロール及びポストロールのため、コストが正しくモデル化され、且つ番組が同じ時間インターバルで他数回にわたり選択される対応するグラフを構築することは些細なことではない。したがって、図５に示されるグラフが構築され、このグラフは、ＰＳＰＲに対する全ての可能なソリューションが得られず、同様に、ソリューションはほぼ最適であることが保証されるのみであるという問題を有する（このことは以下に更に説明される）。図５は、第一のチャネルと中央のタイムラインの表示のみを示す、５分間のプレロール及びポストロールによるケースについて図１の例のグラフを示す。中央のタイムラインでは、ラベル“ｂ”及び“ｅ”は、時間ポイントがＴＶ番組の開始時間又は終了時間を表すかを示し、この場合、更なる下付きは、それぞれのＴＶ番組を示す。つぎに、以下が定義される。
【００８１】
【数２２】
2009516952.tif 000031
全ての時間ポイントのセットは、
【００８２】
【数２３】
2009516952.tif 000032
により与えられる。
【００８３】
さらに、ｔ1＝０，ｔn＝∞及び全てのｉ＝１,…,ｎ−１についてｔi＜ｔi+1により、ｔ1,…,ｔnによりＴにおいて個別の時間ポイントを示す。グラフは、それぞれの時間ポイントｔi，ｉ＝１,…,ｎのノード、及び連続する時間ポイントのそれぞれのペアのエッジ（ｔi,ｔi+1）,ｉ＝１,…,ｎ−１からなる中央のタイムラインを含む。これらのエッジのキャパシティは、ｍに設定され、それらのコストはゼロである。
【００８４】
つぎに、ＴＶチャネルｃ∈Ｃと関連付けされるノード及びエッジが定義される。理論１が示すように、チャネルｃへのチューニングは、ＴＶチャネルｃでの番組が開始する時間ポイントであるか、別のＴＶチャネルでの番組が終了する時間ポイントで開始される。前者のセットの時間ポイントは、Ｔcbで与えられ、後者のセットは、Ｔceにより与えられる。動揺に、チャネルｃへのチューニングは、チャネルｃでの番組が終了するか、別のチャネルでの番組が開始する時間ポイントで停止される。前者のセットは、Ｔceにより与えられ、後者のセットは、
（外８）
2009516952.tif 000033
により与えられる。
【００８５】
同調が時間
（外９）
2009516952.tif 000034
で開始されるとき、受信は、時間εc-1（ｔ）から前方にスケジュールされるＴＶチャネルｃのコンテンツについて確かであり、同調が時間
（外１０）
2009516952.tif 000035
で停止されるとき、これは、受信は、時間λc-1（ｔ）までスケジュールされるＴＶチャネルｃのコンテンツについて確かであることを意味する。したがって、セット
【００８６】
【数２４】
2009516952.tif 000036
が導入され、この時間ポイントから及びこの時間ポイントまでコンテンツが受信されるのが確かであるブロードキャストスケジュールにおける時間ポイントを示す。ここで、増加する順序でｔc1,…,ｔcncによりＴcにおける個別の時間ポイントをナンバリングして、それぞれの時間ポイントｔci，ｉ＝１,…,ｎcについてノードがグラフに導入され、Ｔcにおける連続する時間ポイントのそれぞれのペアについて、キャパシティ１のエッジ（ｔci,ｔc,i+1）,ｉ＝１,…,ｎc−１が導入される。
【００８７】
つぎに、中央のタイムラインとチャネルｃのタイムラインとの間に、全てのキャパシティ１を有するエッジを追加する。このため、中央のタイムラインのそれぞれの時間ポイント
（外１１）
2009516952.tif 000037
からチャネルｃのタイムラインの時間ポイントεc-1（ｔ）にエッジが描かれる。さらに、それぞれの時間ポイント
（外１２）
2009516952.tif 000038
について、チャネルｃのタイムラインの時間ポイントλc-1（ｔ）から中央のタイムラインの時間ポイントｔにエッジが描かれる。
【００８８】
最後に、チャネルｃのタイムラインにおけるエッジ、及び中央のタイムラインへのエッジ並びに中央のタイムラインからのエッジについてコストが定義される。このため、チャネルｃのそれぞれのＴＶ番組ｓ、すなわちｃs＝ｃを考える。ｔci及びｔcjを番組ｓの開始時間及び終了時間とし、すなわちｔci＝ｂs及びｔcj＝ｅsである（なお、これらの時間ポイントは確かにＴcにある）。２つのケースを以下のように区別することができる。
・ｊ−ｉ＝１の場合、エッジ（ｔci,ｔcj）にはコスト−ｖsが与えられる。  
・ｊ−１＞１の場合、以下のようになる。
【００８９】
【数２５】
2009516952.tif 000039
上記以外のエッジは、０のコストを得る。
【００９０】
図５におけるチャネルｃの番組Ａについて、この場合ｂA＝ｔc1及びｅA＝ｔc4であり、５つのタイプのエッジの例は、以下に示される。
（ｉ）ＴＶチャネルｃのエッジ（１８：００，１８：５０）
（ｉｉ）ＴＶチャネルｃのエッジ（１９：１０,１９：３０）
（ｉｉｉ）ＴＶチャネルｃのエッジ（１８：５０,１９：１０）
（ｉｖ）中央のタイムラインからＴＶチャネルｃのタイムラインまでのエッジ（１９：０５,１９：１０）
（ｖ）ＴＶチャネルｃのタイムラインから中央のタイムラインまでのエッジ（１８：５０,１８：５５）。
【００９１】
ここで、ＰＳＰＲを解決するアプローチは、先に構築されたグラフにおけるソースからシンクへのｍの最小コストのフローを発見することである。フローが中央のタイムラインｔi，ｉ＝１,…,ｎを離れる時間ポイントは、ＴＶチャネルへのチューニングが開始するときを示し、フローが中央のタイムラインに戻る時間ポイントは、ＴＶチャネルへのチューニングが停止するときを示す。さらに、１のフローによるＴＶチャネルｃのタイムラインのエッジは、受信された番組の一部を示す。
【００９２】
先の最小コストフロー問題を解くことで、ＰＳＰＲに対するソリューションが与えられるが、１つのソリューションが存在し、ＰＳＰＲに対する全てのソリューションが達成されない。たとえば、３分のプレロール及び５分のポストロールが存在する場合、対応するＴＶチャネルに同調するために選択されたインターバルは、少なくとも８分の長さである。言い換えれば、プレロール及びポストロールを常に得るので、非常に小さなチューニングインターバルを達成することができない。実際に、これは、厳しい制約である。したがって、アルゴリズムは、実際のケースにおいて最適となる。さらに、与えられたグラフは、ビットでリファインされ、これによりこの制約が緩和される。
【００９３】
最後に、部分的な番組が受信されず、完全な番組のみが受信される場合、構築されたグラフは、著しく低減される。次いで、セットＴcは、そのＴＶチャネルでのＴＶ番組の開始時間ポイントｂs及び終了時間ポイントｅsのみを含み、ｊ−ｉ＝１の場合のみがＴＶ番組に適用される。図６は、この問題の例について結果的に得られるグラフを示し、番組ラベルｓをもつエッジはコスト−ｖsを有する。
【００９４】
図７を参照して、ｎ≧１のＴＶ番組の所与のセットを記憶するメモリモジュールからセットＳ（７０１．１）を選択する装置７００が示されており、それぞれのＴＶ番組は、開始時間ｂs及び終了時間ｅs、並びに、全体のＴＶ番組（部分）を得るために長いインターバルが必要とされるように再び定義された値の関数νsを有し、後者の関数は、視聴者又はリコメンダにより提供される。１つのチューナについて、値の関数は、ペナルティをもつ凸関数及び線形関数から構成されるグループから選択される。１を超えるチューナについて、値の関数は、ペナルティをもつ線形関数である。本装置は、Ｍ≧１のチューナにより受信され、おそらく記録される時間マージンをもつ部分的なＴＶ番組を含む最適なセットＳ’⊆Ｓを選択する最小コストネットワークアルゴリズムモジュールを実行するか、該モジュールを自身が更に備えるプロセッサモジュールを更に有する。
【００９５】
ここで図８を参照して、システム８００は、所与の時間インターバル及び所与の視聴者の好みについて部分的なＴＶ番組を含むＴＶ番組の最適なセットを選択するために図７の装置を有し、ＴＶセットでは、到来するブロードキャスト信号７０４は、図７（７００）の装置により選択されたＴＶ番組についてスキャンされ、選択された部分的なＴＶ番組は、チューナ（７０３）により記録され、ＴＶ（８０１）で表示され、全てプロセッサ（７０２）により制御／実行される。
【００９６】
本発明の好適な実施の形態が例示及び記載されたが、本実施の形態で記載されたように、視聴者の好みの値の関数として表現される視聴者の満足度を最大にすることに基づいたプレロール及びポストロールによる部分的なＴＶ番組の最良のセットを選択するためのシステム、装置及び方法は例示するものであり、本発明の真の範囲から逸脱することなしに、様々な変形及び変更が行われ、等価な概念がそのエレメントについて置き換えられることは、当業者により理解されるであろう。さらに、本発明の真の範囲から逸脱することなしに、たとえば様々な最適化アルゴリズムといった、本発明の教示を特定の状況に適合させるために多くの変更が行われる。したがって、本発明は、本発明を実施するために考えられる最良の形態として開示される特定の実施の形態に限定されず、本発明は、特許請求の範囲に含まれる全ての実施の形態を含むことが意図される。
【図面の簡単な説明】
【００９７】
【図１】時間ｔを通して提供される多数のＴＶ番組を例示する図である。
【図２】図１のＴＶ番組の有向グラフである。
【図３】部分的なＴＶ番組を含む図１の例の拡張されたグラフである。
【図４】ＴＶ番組Ａの関連されるエッジのペナルティ及びコストをもつリニアな値関数を有する部分的なＴＶ番組を含む、図１の例の拡張されたグラフである。
【図５】第一のチャネル及び中央のタイムラインからなる表示を示す５分のプレロール及びポストロールをもつケースについて、図１の例のグラフである。
【図６】完全なＴＶ番組のみが受信されるとき、プリロール及びポストロールをもつケースについて、図１の例のグラフである。
【図７】本発明に係る部分的なＴＶ番組の最適な選択の方法を実行する装置を示す図である。
【図８】本発明に従って選択される部分的なＴＶ番組のセットを受信、記録及び表示するシステムを示す図である。
【図１】
2009516952.tif 000040
【図２】
2009516952.tif 000041
【図３】
2009516952.tif 000042
【図４】
2009516952.tif 000043
【図５】
2009516952.tif 000044
【図６】
2009516952.tif 000045
【図７】
2009516952.tif 000046
【図８】
2009516952.tif 000047
【国際調査報告】
2009516952.tif 000048
2009516952.tif 000049