1
$\begingroup$

I want to change the original TSP problem as follows: the cost to visit a city is not related to the previous city that it visited just now, but only on its position in the sequence. Is the problem of finding the minimal cost tour still NP-complete?

$\endgroup$
  • $\begingroup$ the quesiton can also be expressed that" there exist at least one solution to traverse all cities once,but i want to find the solution with lowest cost" $\endgroup$ – yingwan Mar 8 '18 at 13:26
  • $\begingroup$ the original problem is at "cs.stackexchange.com/questions/89092/…" $\endgroup$ – yingwan Mar 9 '18 at 1:25
1
$\begingroup$

Your problem is the same as minimum-weight perfect matching in a bipartite graph. If there are $n$ cities, consider the bipartite graph in which one side consists of vertices $p_1,\ldots,p_n$, the other side consists of vertices $c_1,\ldots,c_n$, and the weight of the edge $(p_i,x_j)$ is the cost of city $j$ at position $i$.

A minimum-weight perfect matching in a bipartite graph can be found efficiently (this is known as the assignment problem). In particular, the problem is not NP-hard unless P=NP.

$\endgroup$
  • $\begingroup$ thanks a lot for your careful explanation,but I have a question that the assignment has a restricted condition that some task must be assigned bofore others, this is to say those tasks have to Satisfies the partial order relation. $\endgroup$ – yingwan Mar 8 '18 at 14:11
  • $\begingroup$ I am a student and meet this problem during my research. Thanks a lot for your kindly reply, Can I have your email so that I can consult you further, My email is wany16@mails.tsinghua.edu.cn $\endgroup$ – yingwan Mar 8 '18 at 14:14
  • $\begingroup$ Now that you know what your problem is called, you can look for the assignment problem with constraints. $\endgroup$ – Yuval Filmus Mar 8 '18 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.