To buy presents for a family Christmas list Mom drives to Store A and Dad drives to Store B.
As more items get added to the list, they must decide who should drive to a new store location to buy the present. How can they minimize total driving distance while kids are randomly adding new items to their list?
The proof above guarantees its possible to never drive more than twice the mileage you would knowing all the items in advance.
The big news is this guarantee works for any number of drivers with any arrangement of gifts.
The algorithm to do this was already known, what we’ve learned is it’s not possible to do any better.
alt Hacker News
To answer that lets get more specific:
To buy presents for a family Christmas list Mom drives to Store A and Dad drives to Store B.
As more items get added to the list, they must decide who should drive to a new store location to buy the present. How can they minimize total driving distance while kids are randomly adding new items to their list?
The proof above guarantees its possible to never drive more than twice the mileage you would knowing all the items in advance.
The big news is this guarantee works for any number of drivers with any arrangement of gifts.
The algorithm to do this was already known, what we’ve learned is it’s not possible to do any better.