The n-vehicle exploration problem is NP-complete
Lists
Only you see this
Abstract
The $n$-vehicle exploration problem (NVEP) is a nonlinear unconstrained optimization problem. Given a fleet of $n$ vehicles with mid-trip refueling technique, the NVEP tries to find a sequence of $n$ vehicles to make one of the vehicles travel the farthest, and at last all the vehicles return to the start point. NVEP has a fractional form of objective function, and its computational complexity of general case remains open. Given a directed graph $G$, it can be reduced in polynomial time to an instance of NVEP. We prove that the graph $G$ has a hamiltonian path if and only if the reduced NVEP instance has a feasible sequence of length at least $n$. Therefore we show that Hamiltonian path $\leq_P$ NVEP, and consequently prove that NVEP is NP-complete.
BibTeX
@misc{cui2023n,
author = {Jinchuan Cui and Xiaoya Li},
title = {{The n-vehicle exploration problem is NP-complete}},
year = {2023},
eprint = {2304.03965},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2304.03965},
}Loading related content...