@techreport{oai:ipsj.ixsq.nii.ac.jp:00031908,
 author = {下田, 善隆 and 高藤, 大介 and 田岡, 智志 and 渡邉, 敏正 and Yoshitaka, Shimoda and Daisuke, Takafuji and Satoshi, Taoka and Toshimasa, Watanabe},
 issue = {92(2003-AL-091)},
 month = {Sep},
 note = {分枝限定法は，さまざまな組合わせ最適化問題を解くための最も一般的な解法である，が問題サイズの増加にともない計算時間が指数関数的に増加する．そのため，計算時間短縮を意図した並列化が考えられる．分枝限定法においては，分枝の早い段階においてり最適解に近い暫定解が得られれば，枝刈りが早く起こる可能性が高くなり計算回数を減らすこと，すなわち，解法の高速化につながる．そこで，上界値計算に高性能な既存近似解法を用いることによって計算回数が減少され，計算時間の短縮が期待できる．また，分枝限定法には，問題中のどの変数を固定するか（分枝変数選択）の選択がある．本稿では，最小重み点被覆問題に対するPCクラスタ上での並列分枝限定法について，上界値計算における近似解法の効果，分枝変数選択の効果を計算機実験により検証する．, Even though a branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems, the computation time is likely to be exponential as the size of input increases. Parallelization is one way of improvement. We can expect that using a better upper bound makes bounding operations appear at early stages of computating, possibly resulting in short computation time. Here we consider using an approximation algorithm in computing an upper bound. In this paper, we experimentally evaluate how using an upper bound given by an existing approximation algorithm and variable selection strategies affect the computation time of a parallel BB for solving the minimun cost vertex cover problem on a PC cluster.},
 title = {最小重み点被覆問題に対する並列分枝限定法の性能評価},
 year = {2003}
}