Path Skyline の計算サーベイ
厳密列挙アルゴリズム
- (1984) On a multicriteria shortest path problem
- Martin's Algorithm (元祖 Label Setting Approach)
- (JACM'91) Multiobjective A*
- 最初に single source でなく point-to-point にして global domination を導入したっぽい
- (EJOR'92) A multicriteria pareto-optimal path algorithm
- multidijkstra (MD)．各コスト単体での距離（→下界）を前計算．
- (SEA'09) Pareto Paths with SHARC
- 前処理してる．次元が増えるとつらそう（変な制約を追加して厳密性を緩和してる）
- (ICDE'10) Route skyline queries: A multi-preference path planning approach
- ARSC
- reference node embedding という前処理により下界を前計算
- (2012) Multiobjective heuristic search in road maps
- クエリごとの前処理系
- (Arxiv'14) ParetoPrep: Fast computation of Path Skylines Queries
- グローバルな前処理はなし，クエリ事の前処理系
- MD とかより良い下界が計算できるから良い，みたいな感じっぽい
- みてない
- (2012) Faster Multiobjective Heuristic Search in Road Maps
- (2011) Multiobjective route planning with precalculated heuristics
- (2012) An Analysis of Some Algorithms and Heuristics for Multiobjective Graph Search
- (2013) A case of pathology in multiobjective heuristic search
その他
OR 系では multi-objective shortest path problem と呼ばれているらしい
- サーベイ
- (2000) A classification of bicriterion shortest path (bsp) algorithms
- (2009) A comparison of solution strategies for biobjective shortest path problems
- (2007) Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms
- (2000) A survey and annotated bibliography of multiobjective combinatorial optimization
- 指数個の Skyline があるので NP-Hard
- (1980) Multiple criteria decision making theory and application
- 相関が強ければ Skyline は少ない
- (2001) Pareto shortest paths is often feasible in practice
- FPTAS
- (1980) Multiple criteria decision making theory and application
- (1987) Approximation of pareto optima in multiple-objective, shortest-path problems
- (2006) Multiobjective optimization: Improved fptas for shortest paths and non-linear objectives with applications.
- 遺伝的アルゴリズム
- (2007) Evolutionary algorithms for the multi-objective shortest path problem
