Processing math: 100%

Proposed by Sascha Van Cauwelaert, Pierre Schaus

Given two vectors of n elements C and P, one can construct a simple graph G with n vertices, such that the directed edge from the vertex i to the vertex ji has a cost equal to C(i)P(j). The distance matrix is therefore the matrix product between the vectors C and P, hence the name of the problem. The problem consists in finding an Hamiltonian circuit of minimum total cost in the graph G. This problem was first described in [plante1987product] and shown to be NP-hard in [sarvanov1980complexity, gilmore1985well].