Maximizar la velocidad y la forma física con el menor número de jugadores

Question

Hay $n$ jugadores de fútbol, cada uno de los cuales tiene una velocidad $s_i\in[0,1]$ y de la salud $f_i\in[0,1]$ . La suma de las velocidades de todos los jugadores es $1$ Y lo mismo ocurre con el fitness. Queremos elegir un subconjunto de jugadores de modo que la suma de velocidades y la suma de aptitudes sean ambas al menos $1/2$ . Sea $a$ sea el tamaño del subconjunto más pequeño.

Supongamos que realizamos el siguiente algoritmo "codicioso": seguir eligiendo jugadores con la máxima suma $s_i+f_i$ hasta que hayamos satisfecho $\sum s_i\geq 1/2$ o $\sum f_i\geq 1/2$ y, a continuación, elegir los jugadores con el máximo atributo posible que aún no hemos satisfecho. Sea $b$ sea el tamaño del conjunto que obtenemos. (Los empates se rompen arbitrariamente).

¿Es cierto que $b/a\leq 3/2$ ¿Siempre? Es posible que $b/a=3/2$ como muestra el ejemplo en el que $n=3$ , $(s_i)=(0.4,0.6,0)$ y $(f_i)=(0.4,0,0.6)$ . El subconjunto de tamaño mínimo es $2$ , eligiendo al segundo y al tercer jugador, pero el algoritmo elige a los tres jugadores. Por otro lado, no es difícil demostrar que $b/a\leq 2$ debe mantenerse (por ejemplo, siguiendo el argumento de Alex Ravsky)

Answer 1

Esta es una construcción con $b/a=2-\tfrac{2}{k+2}\approx 2$ para cualquier número entero $k\geq 2.$ Así que el límite $b/a\leq 2$ es el límite óptimo independiente de $n.$ Tomemos estas categorías de jugadores:

1. un jugador con $(s_i,f_i)=(\tfrac12-\tfrac1{2k},0)$
2. $k$ jugadores con $(s_i,f_i)=(0,\tfrac1{2k})$
3. $k+1$ jugadores con $(s_i,f_i)=(\tfrac1{2k(k+1)},\tfrac1{2(k+1)})$ - nota $s_i+f_i=\tfrac1{2k}$ ici
4. $k(k+1)$ jugadores con $(s_i,f_i)=(\tfrac1{2k(k+1)},0)$

El óptimo se consigue tomando los jugadores de la categoría 1 y 3, totalizando $k+2.$ El algoritmo codicioso tomará al jugador de la categoría 1, pero entonces hay un empate para $s_i+f_i$ entre 2 y 3 y podemos elegir tomar primero todo $k$ jugadores de la categoría 2. Con ello se consigue una aptitud total de $\tfrac 1 2$ por lo que los jugadores restantes se eligen en base a la velocidad y podemos tomar cualquier $k+1$ jugadores de la categoría 3 o 4. Esto da un total de $2k+2$ para el algoritmo codicioso.

Answer 2

Sólo puedo mostrar que $b/a\le 2$ . De hecho, el algoritmo "codicioso" consta de dos fases. Sea $(S,F)$ sea la suma de $(s_i, f_i)$ para todos los pasos de la primera fase. A continuación, ambos $S$ y $F$ son arte menos $1/2$ . Dado que existe un conjunto $Opt$ que consiste en $a$ jugadores de tal manera que $\sum_{j\in Opt} s_j+f_j\ge 1/2+1/2=1$ la avaricia con respecto a $s_i+f_i$ del algoritmo de la primera fase implica que durará como máximo $a$ pasos. Sin pérdida de generalidad podemos suponer que tras el último paso de la primera fase obtenemos la aptitud total de los jugadores elegidos al menos $1/2$ . Dado que existe un conjunto $Opt$ que consiste en $a$ jugadores de tal manera que $\sum_{j\in Opt} s_j\ge 1/2$ la avaricia con respecto a $s_i$ del algoritmo de la segunda fase implica que durará como máximo $a$ pasos. Así, el número total $b$ de pasos del algoritmo es como máximo $a+a=2a$ .

Intenté utilizar enfoques diferentes y más refinados para obtener un mejor límite superior para $b/a$ que $2$ pero, desgraciadamente, todos ellos fracasaron. Tampoco tuve éxito en la construcción de un contraejemplo que diera una mejor cota inferior para $b/a$ que $3/2$ .

Answer 3

Sí.

EDIT: Respuesta en construcción, siéntase libre de ignorar/mejorar.

Supongamos que $A$ el primer conjunto construido de forma óptima con $|A|=a$ y estamos llenando el conjunto $B$ un corredor a la vez con el algoritmo codicioso.

En $a$ corredores elegidos por maximum strength+fitness, habremos cumplido nuestra cuota para $\displaystyle s(B)=\sum_{s_i \in B} s_i$ o para $\displaystyle f(B)=\sum_{f_i \in B} f_i$ . Si no, por la elección de los corredores que ponemos $B$ No. $a$ los corredores pueden tener $\sum s_i+f_i \geq 1$ que asumimos por la existencia de $A$ .

WLOG cumplimos nuestra cuota de $s$ y ahora elegimos a los corredores con la máxima aptitud.

Esto sólo puede tomar $\frac{a}{2}$ más corredores.

Efectivamente, WLOG $A$ consiste en corredores que están dentro de los primeros $\frac{a}{2}$ de la fuerza, la parte superior $\frac{a}{2}$ de la aptitud, o la parte superior $a$ de fuerza+fitness. Si no, puede sustituirlo por un corredor en uno de estos conjuntos sin afectar $A$ de los criterios. <-- Esta es la parte que hay que explicar.

Al elegir a los corredores de la forma en que lo hemos hecho para $B$ incluiremos, por supuesto, la parte superior $a$ para fuerza+fitness y también el top $\frac{a}{2}$ para estar en forma. Si estos no son suficientes para satisfacer la restricción de aptitud, entonces $A$ tampoco podría satisfacer la restricción de aptitud con $a$ corredores, de nuevo una contradicción.