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