A complexity analysis of a ‘pragmatic’ relaxation method for combinatorial optimization with a side constraint

We perform a computational complexity analysis of a heuristic algorithm proposed in the literature for the combinatorial optimization problems extended with a single side-constraint. This algorithm, although such a view was not given in the original work, is a disguised version of an optimal Lagrangian dual solution technique. It also has been observed to be a very efficient heuristic producing near-optimal solutions for the primal problems in some experiments. Especially, the number of iterations grows sublinearly in terms of the network node size so that the heuristic seems to be particularly suitable for the applications such as routing with semi-real time requirements. The goal of this paper is to establish a polynomial worst-case complexity of the algorithm. In particular, the obtained complexity bound supports the sublinear growth of the required iterations.