The assignment problem with nearly Monge arrays and incompatible partner indices

Abstract

In this paper we study the d-dimensional assignment problem in which entries of the cost array satisfy the Monge property, except for infinity-entries, which may violate it. We assume that the infinity-entries are incurred by incompatible partner indices and their number is bounded by an upper bound lambda for each index. We show that the problem can be solved in linear time for fixed d and lambda, and it becomes strongly NP-hard if d or lambda is part of the input. (C) 2016 The Authors. Published by Elsevier B.V.