期刊
DISCRETE APPLIED MATHEMATICS
卷 186, 期 -, 页码 112-127出版社
ELSEVIER
DOI: 10.1016/j.dam.2015.01.004
关键词
Submodular function maximization; Traveling salesman problem; Informative path planning
资金
- Natural Sciences and Engineering Research Council of Canada (NSERC)
In this paper we extend the classic problem of finding the maximum weight Hamiltonian cycle in a graph to the case where the objective is a submodular function of the edges. We consider a greedy algorithm and a 2-matching based algorithm, and we show that they have approximation factors of TIT, and max{2/3(2+kappa), 2/3(1 - kappa)} respectively, where kappa is the curvature of the submodular function. Both algorithms require a number of calls to the submodular function that is cubic to the number of vertices in the graph. We then present a method to solve a multi-objective optimization consisting of both additive edge costs and submodular edge rewards. We provide simulation results to empirically evaluate the performance of the algorithms. Finally, we demonstrate an application in monitoring an environment using an autonomous mobile sensor, where the sensing reward is related to the entropy reduction of a given set of measurements. (C) 2015 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据