Right order of elements

16 Views Asked by At

Compute in which order n contestants of a triathlon should be sent on their way such as to minimize the (expected) completion time , which is the earliest moment everyone is finished. The triathlon consists of first swimming in the pool, then biking a certain distance, and finally running a small distance. Biking and running can be done simultaneously, but the pool can be used only by one contestant at a time. From previous competitions, there is data on the expected times for each of the contestants and for each of the three activities: for $ i= 1, . . . , n$ , let $w_i$, $b_i$, and $r_i$ be the time contestant $i$ requires for swimming, biking and running, respectively. The answer is that the right ordering is by decreasing $b_i$ + $r_i$. My question is can we apply machine learning technique to solve the problem: let $R_1, ..., R_n$ be a set where $R_i = w_i + b_i + r_i$. Then we know that the time that the $i$-th contestant needs to finish the triathlon is $R_i + \sum_{j=1}^{i-1} w_j$, which kind of resembles linear classifier. Total triathlon time is then $max(R_i + \sum_{i=1}^{i-1} w_j.)$ and our goal is to find and ordering that gets us $min(max(R_i + \sum_{i=1}^{i-1} w_j.))$.