Communication complexity of turnpike problem - Buño, Kelvin C.
The aim of this research is to acquire a communication complexity for the Turnpike Reconstruction Problem. The Turnpike Reconstruction Problem is a set reconstruction problem of one dimension. We create a communication protocol to solve the problem and we show that the communication complexity of a one-way two-party communication model is n - 1 and 2n - 3, where n is the number of points that define the input multiset. This is in contrast to a protocol that has a communication complexity in terms of [( n/2)]. We also show that the Turnpike problem can also be extended to a three-party communication model and its communication complexity is 2n - 2. The research also concludes that it can still be extended to k-party communication, where k can be a multiple of the [( n/2)] elements of the input multiset.