Optimization Online


The constant objective value property for combinatorial optimization problems

Ante Custic(custic***at***opt.math.tugraz.at)
Bettina Klinz(klinz***at***opt.math.tugraz.at)

Abstract: Given a combinatorial optimization problem, we aim at characterizing the set of all instances for which every feasible solution has the same objective value. Our central result deals with multi-dimensional assignment problems. We show that for the axial and for the planar $d$-dimensional assignment problem instances with constant objective value property are characterized by sum-decomposable arrays. We provide a counterexample to show that the result does not carry over to general $d$-dimensional assignment problems. Our result for the axial $d$-dimensional assignment problems can be shown to carry over to the axial $d$-dimensional transportation problem. Moreover, we obtain characterizations when the constant objective value property holds for the minimum spanning tree problem, the shortest path problem and the minimum weight maximum cardinality matching problem.

Keywords: Constant objective value; admissible transformation; multi-dimensional assignment problem; sum-decomposable array.

Category 1: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 05/21/2014
Entry Accepted: 05/21/2014
Entry Last Modified: 05/21/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society