Given a system and a set of strongest security measures, a system administrator wants to optimally place these strongest security measures in appropriate places in the system to minimize the maximum damage caused by a potential attacker who comes with a budget B. In this article we model this scenario as follows. Let T be a network in the system with cost and prize assignments to edges and nodes, respectively. The problem of determining k appropriate edges for the k strongest security measures in the security system was shown to be coNP-hard, implying that a deterministic polynomial time algorithm most likely does not exist. We propose three methods to solve this problem. Here \(d=deg(r)\) is the root degree, n is the number of non-root vertices, \(c_{max}\) is the maximum edge cost, and \(L=\sum _{v\ne r} p(v)\) is the total prize over all non-root nodes. First, conditioned on some reasonable assumptions and given any error constant \(\frac{1}{B}\le \epsilon \le 1\) , a polynomial time ( \(1+\epsilon \) )-approximation algorithm with a time bound \(O(d^2n(c_{max}n)^2)\) is given. This approximation algorithm is fast and gives a reasonably good result. Second, given \(B\le c_{max}n\) , a \(O(d^2n(c_{max}n)^2)\) time algorithm is shown to give the exact solution to the problem. Third, given an error rate \(\epsilon > 0\) and an accuracy parameter \(k' \le k\) , the \((1+\epsilon )^{k-k'}\) polynomial time approximation scheme is shown to solve the problem. The third approximation scheme has the running time of \(O((k-k')\frac{1}{\epsilon ^2}n^4\log L)\) . Consequently, we resolve the open problem posed by Mukdasanit and Kantabutra [18] concerning the case of placing k infinite costs on k edges.
