A polynomial-time algorithm to the combinatorial optimization interdiction problemwith sum-type objective functions

A combinatorial optimization problem is to find an optimalobject among a finite number of objects having commonstructure. The utility of an object is measured by a utilityfunction. The class of combinatorial optimization problem isa wide category of optimization problems. For example, itcontains shortest path problems, minimum spanning treeproblems, maximum matching problems, and etc.A natural extension of combinatorial optimization problemsis that there exists a proactive adversary that wants toprevent optimizing the objective function. For this purpose,he can change some coefficients of the objective function byincurring a cost proportional to the magnitude of changes.This paper considers this problem, called combinatorialoptimization interdiction problem, in the situation that thereare bound and budget constraints which the adversary mustrespect them. The paper presents an algorithm for solvingthe problem. In the special circumstances, it is shown thatthe complexity of the proposed algorithm is polynomial time.