巡回セールスマン問題（ＴＳＰ）は特殊な数学パズルではなく，半導体チップの穿孔，遺伝子情報の染色体上の配置，データのＤＶＤ上の配置，など実際への応用がたくさんある．

　それまで解かれていない難問を解くと大々的に報じられ、研究者の間で騒ぎになる．しかしながら，ＴＳＰについては多項式時間のアルゴリズムは知られていない．これまでの最善の結果は１９３２年に発表されたＯ（ｎ^2２^n）で計算する解法である．

　（その１）で紹介した巡回セールスマン多面体（ＴＳＰ多面体）とは，完全グラフＫnのことではなく，ｎ点の凸包のことであって，ミンコフスキーの定理がいっていることは，ＴＳＰが線形計画法として正確にモデル化できるという事実にほかならない．そして，ＴＳＰ多面体のファセットは半空間を表す不等式によって面取りされるのである．

　それため，

　　［参］クック「驚きの数学巡回セールスマン問題」青土社

には

　　［参］フバータル「線形計画法」啓学出版

　　［参］ツィーグラー「凸多面体の数学」シュプリンガー・フェアラーク東京

について，書評が載っているわけである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝