The n-vehicle exploration problem is NP-complete
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909315448700928 |
|---|---|
| author | Cui, Jinchuan Li, Xiaoya |
| author_facet | Cui, Jinchuan Li, Xiaoya |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_03965 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The n-vehicle exploration problem is NP-complete Cui, Jinchuan Li, Xiaoya Computational Complexity 68Q17, 90C27 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. |
| title | The n-vehicle exploration problem is NP-complete |
| topic | Computational Complexity 68Q17, 90C27 |
| url | https://arxiv.org/abs/2304.03965 |