CRICKET is NP-Complete

How do we decide the order of batsmen to maximize the cumulative runs made by them in 50 overs ? Here is my perspective......

Let's say we have the following statistics of batsmen based on their past performances.

• average time spent by a batsman on the field.
• average runs per over made (during past partnerships) for each pair of batsmen.

Given this data, we would like to decide the order of batsmen to maximize their runs (assuming they don't deviate much from their average past performance).

Formally speaking, we have a complete undirected weighted (vertex-weighted and edge-weighted) graph on n vertices. The vertices represent the batsmen and the weights on the vertices indicate the average time spent by the batsman on the field. The weight w on the edge (u,v) represents the average runs per over made (during past partnerships) by (u,v). That is, if u and v are playing on the field, they can together contribute at the rate of w runs per over. Having a bad partner hurts you, even if you are a high-scorer.

For example, the input graph can be as shown below...




The best schedule for m (=50) overs can be as shown below....



In the above figure, we have two rows representing the two batsmen on the field at any given time. The number of runs for the above schedule is derived by adding the length-of-overlap*edge-weight for each pair of players.

Theorem : Given the input graph G(V,E), finding the optimum (maximizing runs) schedule is NP-Complete.

I will post the proof at a later time in a later post. In the menwhile, you can try your own approaches to prove it. The next obvious question is about the approximability.

This model might not be pratical (due to noise, does not take other factors (like the skills of bowlers and bowler's schedule) into account) in real-life, but serves as a good mathematical puzzle.

P.S. Beginners can read the rules of cricket here. World Cup 2007 Schedule is here. Add this cool countdown to world cup to your google personalized homepage.