An O(nlogn/logw) Time Algorithm for Ridesharing

Yijie Han and Chen Sun

Computer and Information Science, 2021, vol. 14, issue 1, 8

Abstract: In the ridesharing problem different people share private vehicles because they have similar itineraries. The objective of solving the ridesharing problem is to minimize the number of drivers needed to carry all load to the destination. The general case of ridesharing problem is NP-complete. For the special case where the network is a chain and the destination is the leftmost vertex of the chain, we present an O(nlogn/logw) time algorithm for the ridesharing problem, where w is the word length used in the algorithm and is at least logn. Previous achieved algorithm for this case requires O(nlogn) time.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.ccsenet.org/journal/index.php/cis/article/download/0/0/44549/47014 (application/pdf)
http://www.ccsenet.org/journal/index.php/cis/article/view/0/44549 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ibn:cisjnl:v:14:y:2021:i:1:p:8

Access Statistics for this article

More articles in Computer and Information Science from Canadian Center of Science and Education Contact information at EDIRC.
Bibliographic data for series maintained by Canadian Center of Science and Education ().