The initial scores in the four reviews were all in favour of accepting, although not strongly. The paper studies a relevant problem, presenting a new algorithm with performance guarantees and almost matching lower bounds. However some questions were raised regarding, for example, connections to other work and practical algorithms, and also more technical issues. The authors provided a detailed reply. After discussion among the reviewers, their concerns were partially answered, leading to somewhat stronger support for accepting.