4 ms·
This is an important result, sometimes called the holy grail of competitive analysis. One way to think about competitive analysis is bulk discounts. In life we
by WhitneyLand 11d ago
This is an important result, sometimes called the holy grail of competitive analysis.
One way to think about competitive analysis is bulk discounts. In life we’re constantly having to choose between quantity and discount. We could buy 1 item for a higher price, or say quantity 5 or 10 to get better discounts. The problem comes when we don’t know in advance exactly how many we’re going to need.
What should be our strategy for choosing how many to buy, and whatever the strategy is how well does it compare with having perfect knowledge upfront?
- emil-lp 11d agoOr while waiting for the bus: if it's late, when should you start walking instead?
- petesergeant 11d agoFor the layman, does this result give us an optimal solution to problems like this? Is it easily explained?
- WhitneyLand 11d agoTo 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.