The Marathon Problem has been widely used as a standard benchmark for measuring a person's fitness. An instance of marathon contains a path (not necessarily simple) on a elliptic graph with total distance of 42.195 km (~26 miles). The decision problem for marathon is to check if any human being can finish an instance of marathon with a given time limit, whilst the optimization problem is to minimize the time. The Marathon Problem is decidable unless some human beings are immortal. The problem has been studied extensively for more than 2000 years. Pheidippides (Athens, AD 1) [1] first showed that the decision problem is always feasible with a finite time limit, unfortunately he was unable to reproduce his great result. Louis (Athens, 1896) gave an approximation schema with an absolute performance guarantee of 3 hours. Recently, Gebrselassie (Berlin, 2008) showed empirically that there exists some human being who can finish a marathon within 2 hours and 4 minutes. However, the set of human being is too large and different human beings differ greatly. It naturally leads to a question that if there exists any bounds for some families of human being (for instances, the set of graduate students in Computer Science, the set of small and short people, etc).

To obtain a more comprehensive understand of the marthon problem, we perform a qualitative study on a specific instance, i.e. if Justin Yip can finish some instance of marathon within 4 hours before getting his PhD. This instance is particularly interesting since the specimen is a PhD candidates who codes 12 hours a day and 7 days a week before the paper deadline and on the other hand takes a 6-weeks vacation in the summer. He is small and short, but consumes surprisingly large amount of food daily. His personal motto is William Hung's favorite quote: "I already gave my best, and I have no regrets at all". If this study gives positive results, it will be a solid foundation block for finding bounds for some aforementioned families of human being.


Figure 1. Reguar running path. View Larger Map

It is a long term project started in March 2009. Figure 1 shows his regular running path, notice that sometimes he runs on Blackstone Bullevard twice, and sometimes he starts running at Wayland avenue near his home. To date, we gathered some preliminary results (a) the specimen is more likely to give up if he runs alone, (b) the specimen can run more than 10 km every other day, (c) running with either iPhone or first generation of iPod nano is terrible, while the new iPod shuffle is a great running companion [2] and (d) running does not help his sleeping problem.

The greatest challenge of this research is to ensure the specimen runs regularly, because he is always distracted by some short-term research projects (like Tetris, Length-Lex, Lobsters etc).

You can contribute to this project by running with him, sponsoring him, praising him, intimidating him, making him food or whatever you can think of. Any contribution is greatly appreciated.

[1] Wiki Marathon
[2] J. Yip, The unbearable heaviness of running, work in progress, 2009

I love tetris. I devote most of my research hours on this project.

Precisely, tetris is an online stochastic combinatorial optimization problem under severe time constraint. There is a set of states that there is no room to allocate a new block from the top, and we call this set GameOverSet. GameOverSet is the fixed point of this problem, according to the game mechanism, it is guaranteed to reach a fixed point. The goal is to maximize the objective function (the Score) before reaching the fixed point. The problem is a hard combinatorial problem, even offline deterministic version of tetris (the block sequence is know before the game starts) is already NP-hard. Usually this problem is under a time constraint that severely limit the number of offline optimization can be computed and the number of keystroke can be achieved. The size of the time window is inversely proportional to the current score, the score is however a monotonic increasing function, it makes the problem become harder in the latter stages of the game. The offline optimization algorithm in my brain gives a sequence of actions to be made (usually in form of keystrokes) in response to a new block. However the actual action is prone to error that there is a non-zero probability of pressing the wrong key. Hence the algorithm must be robust enough to handle such exceptional conditions.

The algorithm includes some parameter tuning. The algorithm can decide the initial level (the inital size of time window). The score awarded of each operation is the multiple of the level. The higher the level, the higher the score awarded (however, the smaller the time window), the current state-of-the-art algorithm starts at level 12.

The empirical result shows that solving the problem after 6pm usually gives better results.

(Update on Dec2, 2008, I feel that I have reached my local optimum in the problem, hence this project is completed.)