up vote -1 down vote favorite
1

A graph with positive edges is given along with several vehicles at specific vertices of the graph.One of the vehicles has a package that is required to be transferred to a destination node.The package can be exchanged from vehicle to vehicle even within the edges.Vehicles have speed and fuel consumption(we can assume that they have infinite fuel and each car consumes different amounts of fuel for each unit traversed). Is the problem of minimizing the ordered tuple of (total time,fuel consumption) NP complete?

share|cite|improve this question
  • 1
    It is polynomial-time solvable for a constant number of vehicles, not sure what happens when there are more. – Chao Xu yesterday
  • There is a paper published recently that 'proves' that this is np complete using a planar 3 sat reduction – GEP yesterday
  • 1
    Please add a link to the paper in the question description. – Chao Xu yesterday
  • 1
    @GEP So you are asking a question you know the answer to? Also what does it mean to minimize a tuple? Do you mean minimize in lex-order? – Sasho Nikolov yesterday

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.