An O(nlogn/logw) Time Algorithm for Ridesharing

摘要

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.