Three algorithms for finding mines in a line



We introduce three algorithms for the problem of finding mines in a line. In this problem we are given a line partitioned into small segments, the time taken
to either search in or travel through each segment, as well as a score value assigned to each segment. The goal is to choose the segments to visit such that the sum of the corresponding scores is maximized and the total travel and search time is minimized. The two algorithms are based on dynamic programming approaches for the multi-criteria knapsack problem. The third algorithm solves
a bi-criteria shortest path problem formulation.


24th European Conference on Operational Research (EURO XXIV), July 2010

Cited by

No citations found