Maximizing speed and fitness with fewest players
Here is a construction with $b/a=2-\tfrac{2}{k+2}\approx 2$ for any integer $k\geq 2.$ So the bound $b/a\leq 2$ is the optimum bound independent of $n.$ Take these categories of players:
- one player with $(s_i,f_i)=(\tfrac12-\tfrac1{2k},0)$
- $k$ players with $(s_i,f_i)=(0,\tfrac1{2k})$
- $k+1$ players with $(s_i,f_i)=(\tfrac1{2k(k+1)},\tfrac1{2(k+1)})$ - note $s_i+f_i=\tfrac1{2k}$ here
- $k(k+1)$ players with $(s_i,f_i)=(\tfrac1{2k(k+1)},0)$
The optimum is achieved by taking the players from category 1 and 3, totalling $k+2.$ The greedy algorithm will take the player from category 1 but there is then a tie for $s_i+f_i$ between 2 and 3 and we can choose to first take all $k$ players from category 2. This achieves a total fitness of $\tfrac 1 2$ so the remaining players are chosen based on speed and we can take any $k+1$ players from category 3 or 4. This gives a total of $2k+2$ for the greedy algorithm.