Article ID Journal Published Year Pages File Type
1141412 Discrete Optimization 2016 13 Pages PDF
Abstract

An instance of a combinatorial optimization problem is said to have the constant objective value property (COVP) if every feasible solution has the same objective function value. In this paper our goal is to characterize the set of all instances with the COVP for multidimensional assignment problems.Our central result deals with planar dd-dimensional assignment problems. We show that such constant objective value instances are characterized by so-called sum-decomposable arrays with appropriate parameters. This adds to the known result for the axial dd-dimensional case.

Related Topics
Physical Sciences and Engineering Mathematics Control and Optimization
Authors
, ,