On efficient algorithms for finding efficient salvo policies

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability p_i: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP-complete.