Search

Bike-sharing systems usually suffer from out-of-service events due to bike underflow or overflow. We propose to recruit workers to rebalance station loads. We partition the complex rebalancing problem in temporal and spatial domains. The temporal domain is divided into a sequence of slices with a fixed duration. In each slice, we allocate a pair of overflow/underflow stations to a worker such that the cost is minimized, which is NP-hard. A 3-approximation algorithm is proposed. We further investigate the worker shortage case and extend the matching algorithm to consider the number of unsatisfied users. Then, the configuration dynamic in the sequence of slices is captured by determining the rebalancing target for each rebalancing operation. We investigate heuristic approaches to minimize the total number of bike movements. Furthermore, we extend our scheme to dockless BSSs using clustering techniques. We simulate our algorithms on both real-world and synthetic datasets. Experiment results show that our approaches can reduce the average total detour per slice. In worker shortage, considering the number of unsatisfied users could improve the long-term performance of rebalancing. Besides, we find that our scheme could maintain worker satisfaction over multiple time slices, which indicates the sustainability of our rebalancing scheme.

Due to the additive property of most machine learning objective functions, the training can be distributed to multiple machines. Distributed machine learning is an efficient way to deal with the rapid growth of data volume at the cost of extra inter-machine communication. One common implementation is the parameter server system which contains two types of nodes: worker nodes, which are used for calculating updates, and server nodes, which are used for maintaining parameters. We observe that inefficient communication between workers and servers may slow down the system. Therefore, we propose a graph partition problem to partition data among workers and parameters among servers such that the total training time is minimized. Our problem is NP-Complete. We investigate a two-step heuristic approach that first partitions data, and then partitions parameters. We consider the trade-off between partition time and the saving in training time. Besides, we adopt a multilevel graph partition approach to fit the bipartite graph partitioning. We implement both approaches based on an open-source parameter server platform—PS-lite. Experiment results on synthetic and real-world datasets show that both approaches could significantly improve the communication efficiency up to 14 times compared with the random partition.