In this paper, we focus on extended Kantorovich norms, which seem to be much more flexible than many other «metrics» deriving from optimal mass transport problems. General theoretical results are recalled, and the discrete case is investigated, especially from a computational point of view. An efficient algorithm is then introduced to solve the related linear programming problem, and possible applications are discussed.