# Finding mines in a Line

### Authors

### Abstract

We discuss solution approaches for the following problem: Given a line partitioned into segments,each segment is assigned the time taken to either search in or travel through it, as well as a score

value representing the probability to find a mine there. The goal is to choose the segments to visit

such that the sum of the scores is maximized while the total time spent is minimized. We compare different dynamic programming approaches to determine the non-dominated set of the

problem that are based on the modeling of the problem as a knapsack as well as a shortest-path

problem.