On the Depth of Combinatorial Optimization Problems

Kern, Walter (1993) On the Depth of Combinatorial Optimization Problems.
Published in: Discrete applied mathematics Vol. 43 (2). pp. 115-129.


This paper studies the notion of 'depth' of a combinatorial optimization problem, which has already been touched on by several other authors. This notion can be defined as follows: Consider a discrete optimization problem min{c(x)colon xin X}. Usually, hill climbing algorithms work as follows: First, a neighbourhood structure has to be specified on X. Then, starting from an arbitrary solution, say xsb 0, one constructs a sequence xsb 0,xsb 1,xsb 2,cdots (hopefully leading to an optimum) such that xsb i is a neighbour of xsb {i-1} for all i. For xsb 0in X, the depth d(xsb 0) is defined to be the smallest dgeq 0 such that there exists a sequence xsb 0,xsb 1,cdots,xsb n with c(xsb n)<c(xsb 0) and all intermediate solutions xsb i having objective value c(xsb i)leq c(xsb 0)+d. The depth of the problem is defined to be the maximum depth of a solution xsb 0in X. This notion plays an important role in the theory of simulated annealing. Here we show that the depth is of some interest in its own right. We prove some upper bounds and investigate the computational complexity of the depth function for some selected examples.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr86-033
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 20 Oct 2011 15:19
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/33