Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems

The authors gratefully acknowledge the collaboration with Motivate (the company operating Citi Bike) and the comments of A. Shioura, who identified a false claim in an earlier version of the manuscript. The authors also thank anonymous reviewers and editors for suggestions that improved the paper throughout several revisions. A preliminary version of this paper, including parts of the first three sections, appeared in the proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO 2017).