Paper accepted at journal ACM Transactions on Algorithms