7B-03
グラフのスクールバス問題とその一般化
○清野裕崇,畑中達彦,伊藤健洋,周  暁(東北大)
グラフのスクールバス問題とは,複数台のバスの経路を策定する問題である.グラフのいくつかの点には生徒が割り当てられており,1点が学校に対応する.各生徒は,自身の点から学校までの最短距離と比べて,バスで遠回りした移動距離を不満度として持ち,その最大の不満度を最小化する経路を求めたい.本稿では,近似アルゴリズムの観点から研究を行う.具体的には,この問題はバスの台数が定数であっても,一般にはAPX困難であることを示した上で,木に対しては多項式時間の完全近似スキームを与えた.

footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会