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$
2
  • $\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, 2018 at 13:26
  • $\begingroup$ the original problem is at "cs.stackexchange.com/questions/89092/…" $\endgroup$
    – yingwan
    Mar 9, 2018 at 1:25

1 Answer 1

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$
3
  • $\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, 2018 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 [email protected] $\endgroup$
    – yingwan
    Mar 8, 2018 at 14:14
  • $\begingroup$ Now that you know what your problem is called, you can look for the assignment problem with constraints. $\endgroup$ Mar 8, 2018 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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