Network Design Problem

　最大フロー問題の前提は、ある頂点に着目したときに頂点の流入量と流出量は等しくなければならない。ただし、ストリーム処理においては、フィルタリング等あるので、基本的には流入量に対して流出量はある割合で小さくなる。ある頂点同士を結ぶ容量（バンド幅）が決まっており、最大フロー問題のように、ある頂点から複数の頂点に分岐して流すことも許す。また、複数のストリームプログラムが走っており、各ストリームプログラムを構成するオペレータの間引き率は決まっているとする。また、フローネットワーク（容量が決まっている）も事前に与えられるものとする。このような前提が与えれたときに、走らせられるジョブ（ストリームプログラム）の最大数を求めよ、というのが問題。間引き率が 1 のときは Network Design Problem として知られており、NP-Hard. 但し、当然、ネットワークが小さいときにはヒューリスティックが知られている。上記の問題はNetwork Design Problem よりも難しいので、NP-Hard. もし実用上問題なく動くような手法が考案できれば、我々の領域では新規性が高いだろう。