22
$\begingroup$

There are $n$ football players, each of whom has a speed $s_i\in[0,1]$ and fitness $f_i\in[0,1]$. The sum of the speeds of all players is $1$, and the same is true for fitness. We want to choose a subset of players so that the sum of speeds and the sum of fitnesses are both at least $1/2$. Let $a$ be the size of the smallest such subset.

Suppose we perform the following "greedy" algorithm: keep picking players with the maximum sum $s_i+f_i$, until either we have satisfied $\sum s_i\geq 1/2$ or $\sum f_i\geq 1/2$, and then pick the players with the maximum possible attribute that we haven't satisfied yet. Let $b$ be the size of the set we get. (Ties are broken arbitrarily.)

Is it true that $b/a\leq 3/2$ always? It is possible that $b/a=3/2$, as shown by the example where $n=3$, $(s_i)=(0.4,0.6,0)$ and $(f_i)=(0.4,0,0.6)$. The minimum-size subset is $2$, by picking the 2nd and 3rd players, but the algorithm picks all three players. On the other hand, it is not hard to show that $b/a\leq 2$ must hold (e.g. following Alex Ravsky's argument)

$\endgroup$
  • $\begingroup$ By "size of subset", you mean the number of elements in the subset or the sum of the elements in the subset? $\endgroup$ – DanielV Jul 29 '16 at 21:39
  • $\begingroup$ I mean the number of elements. $\endgroup$ – Karo Jul 29 '16 at 21:42
  • $\begingroup$ I don't think your greedy algorithm is completely specified. How does it deal with ties in $s_i + f_i$? There is such a tie in your example, and it's not clear how it picks among the first 3 players. $\endgroup$ – Daniel Weissman Aug 4 '16 at 1:22
  • $\begingroup$ The algorithm breaks ties arbitrarily. So the question is whether the approximation holds no matter how ties are broken. $\endgroup$ – Karo Aug 4 '16 at 6:31
2
$\begingroup$

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:

  1. one player with $(s_i,f_i)=(\tfrac12-\tfrac1{2k},0)$
  2. $k$ players with $(s_i,f_i)=(0,\tfrac1{2k})$
  3. $k+1$ players with $(s_i,f_i)=(\tfrac1{2k(k+1)},\tfrac1{2(k+1)})$ - note $s_i+f_i=\tfrac1{2k}$ here
  4. $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.

$\endgroup$
0
$\begingroup$

Yes.

EDIT: Answer under construction, feel free to ignore/improve.

Suppose $A$ the first set constructed optimally with $|A|=a$, and we are filling the set $B$ one runner at a time with the greedy algorithm.

Within $a$ runners chosen by maximum strength+fitness, we will have met out quota for $\displaystyle s(B)=\sum_{s_i \in B} s_i$ or for $\displaystyle f(B)=\sum_{f_i \in B} f_i$. If not, then by the choice of the runners we put in $B$, no $a$ runners can have $\sum s_i+f_i \geq 1$, which we assumed by existence of $A$.

WLOG we met our quota for $s$, and we now pick runners with maximum fitness.

This can only take $\frac{a}{2}$ more runners.

Indeed, WLOG $A$ consists of runners who are within the top $\frac{a}{2}$ of strength, top $\frac{a}{2}$ of fitness, or top $a$ of strength+fitness. If not, can replace him for a runner in one of these sets without affecting $A$'s satisfaction of the criteria. <-- This is the bit that needs explaining.

By choosing the runners the way we have done for $B$ we will ecrtainly include the top $a$ for strength+fitness and also the top $\frac{a}{2}$ for fitness. If these are not sufficient to satisfy the fitness restriction then $A$ could also not satisfy the fitness restriction with $a$ runners, again a contradiction.

$\endgroup$
0
$\begingroup$

I can only show that $b/a\le 2$. Indeed, the “greedy” algorithm consists of two phases. Let $(S,F)$ be the sum of $(s_i, f_i)$ for all steps of the first phase. Then both $S$ and $F$ are art least $1/2$. Since there exists a set $Opt$ consisting of $a$ players such that $\sum_{j\in Opt} s_j+f_j\ge 1/2+1/2=1$, the greed with respect to $s_i+f_i$ of the first phase algorithm implies that it will last at most $a$ steps. Without loss of generality we may assume that after the last step of the first phase we get the total fitness of the chosen players at least $1/2$. Since there exists a set $Opt$ consisting of $a$ players such that $\sum_{j\in Opt} s_j\ge 1/2$, the greed with respect to $s_i$ of the second phase algorithm implies that it will last at most $a$ steps. Thus the total number $b$ of steps of the algorithm is at most $a+a=2a$.

I tried to use different and more refined approaches to obtain a better upper bound for $b/a$ than $2$, but, unfortunately, all of them failed. Also I had no success in the construction of a counterexample yielding a better lower bound for $b/a$ than $3/2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.