「Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications ...」の編集履歴（バックアップ）一覧はこちら

「Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications ...」(2014/10/03 (金) 17:46:29) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* 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 and Applications to Distance-Constrained Vehicle Routing
* 概要
- 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+ε近似でとける
- 

* 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+ε近似でとける

&tags()

&update()