首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Probing a Set of Trajectories to Maximize Captured Information
  • 本地全文:下载
  • 作者:S{'a}ndor P. Fekete ; Alexander Hill ; Dominik Krupke
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:160
  • 页码:5:1-5:14
  • DOI:10.4230/LIPIcs.SEA.2020.5
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set T of trajectories in the plane, and an integer k≥ 2, we seek to compute a set of k points ("portals") to maximize the total weight of all subtrajectories of T between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances.
  • 关键词:Algorithm engineering; optimization; complexity; approximation; trajectories
国家哲学社会科学文献中心版权所有