Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications ... - todo314 @ ウィキ

Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing

• Zachary Friggstad, Chaitanya Swamy
• STOC 2014

概要

• Approximation Algorithms for Regret-Bounded Vehicle Routingについて
• 30.86近似アルゴリズム
• 今までO(log n)近似

RVRP

• 入力
  • 完全グラフ
  • 距離
    • 三角不等式
  • 始点r
  • 整数R
• rを始点とするパスの集合で次を満たす
  • 全頂点が少なくとも1つに被覆されている
  • 各頂点vについて，(パスに沿った距離) ≦ d(r,v)+R
• パスの本数を最小化したい
• Regret Distance
  • 損する分
• RVRPは以下と同値
  • rを始点とする(Regret Distance)長さR以下のパスの集合で全頂点覆いたい
  • パスの数を最小化

• 補題2.2
  • 1本あった時に，それを程よく分割するとα本にできる
• だから，長さの和の最小化だけを考える

アルゴリズム

• LP緩和→近似→整数丸め
• LPは双対を考えれば(Orienteering)2+ε近似でとける

STOC

2014-10-03 17:46:29 (Fri)