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

http://www.crm.umontreal.ca/CanaDAM2009/pdf/meszaros.pdf