Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141412 | Discrete Optimization | 2016 | 13 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Ante Ćustić, Bettina Klinz,