Budget and Profit Approximations for Spanning Tree Interdiction

Rafail Ostrovsky, Yuval Rabani, Yoav Siman Tov

We give polynomial time logarithmic approximation guarantees for the budget minimization, as well as for the profit maximization versions of minimum spanning tree interdiction. In…