# Optimization problems

1. Nov 23, 2005

### kleinwolf

There are two famous NP optimization problems :
1) traveling salesman : find the shortest path in a graph, through all vertices. Without boundary conditions, this is : $$min_{\sigma\in Perm(\mathbb{N}_n)}\sum_{i=1}^{N-1}a_{\sigma(i),\sigma(j)}$$ where there are $$n$$ cities, and the distance between cities $$i$$ and $$j$$ is $$a_{ij}$$..and $$\sigma$$ is just a permutation of the cities order.
2) coin-changing problem : the less coins you need to make up to a given sum S in a given coin system $$\left(v_i\right)_{i=1}^k$$ : $$\tilde{\min}_{n} \left(\sum_{i=1}^n v_{f(i)}=S\right)$$ where $$f : \mathbb{N}_n\rightarrow \mathbb{N}_k$$ with $$v_f(i)$$ is giving the index of the ith coin needed. $$\tilde{min}$$ gives the minimal n, If n does not exist, then it is $$\infty$$.
I thinnk there should exist a forumla betwen those two problems : the coin system is equivalent to the distances between cities (kind of constraint), but I cannot firgure it out..could somebody help ?

Last edited: Nov 23, 2005