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$
4
  • $\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, 2016 at 21:39
  • $\begingroup$ I mean the number of elements. $\endgroup$
    – user336268
    Jul 29, 2016 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$ Aug 4, 2016 at 1:22
  • $\begingroup$ The algorithm breaks ties arbitrarily. So the question is whether the approximation holds no matter how ties are broken. $\endgroup$
    – user336268
    Aug 4, 2016 at 6:31

3 Answers 3

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
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .