Friday, January 28, 2011

Pizza Cutting Problem (Challenging Problem)

Theorem :

There is an algorithm that, given a cutting of the pizza with n slices, performs a precomputation in time O(n). Then, during the game, the algorithm decides each of Alice’s turns in time O(1) in such a way that Alice makes at most two jumps and her gain is at least g(n)|P|.

Claim :

There is an algorithm that, given a cutting of the pizza with n slices, computes an optimal strategy for each of the two players in time O(n^2). The algorithm stores an optimal turn of the player on turn for all the n^2−n+2 possible positions of the game.



Open problem

Is there an algorithm that uses o(n^2) time for some precomputations and then computes each optimal turn in constant time?

See details


No comments:

Post a Comment