CISUC

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.

Conference

16th European Conference on Mathematics for Industry (ECMI 2010), July 2010


Cited by

No citations found