k-server: confirman la conjetura tras 38 años de búsqueda

Por qué el paper de Coester, Koutsoupias y Zbysiński sacude a la computación teórica

El 14 de septiembre de 2026, Christian Coester, Elias Koutsoupias y Marek Zbysiński subieron a arXiv el paper The k-server conjecture is true (arXiv:2609.15979), cerrando un problema abierto durante 38 años y considerado durante décadas el «santo grial» de los algoritmos en línea. Su resultado: el work function algorithm (WFA) es k-competitivo en cualquier espacio métrico, exactamente la cota que la conjetura sospechaba y que ningún algoritmo determinista había podido demostrar de forma general.

El paper, de 22 KB, no es incremental: resuelve la pregunta formulada en 1988 por Mark Manasse, Lyle McGeoch y Daniel Sleator en Competitive algorithms for on-line problems (STOC '88), un paper citado en prácticamente todo el campo de la competitive analysis. Lo notable, además del resultado, es que los propios autores reconocen en los agradecimientos que la prueba se gestó con ayuda de modelos de IA conversacional, un detalle relevante para founders que construyen productos sobre LLMs.

Qué es el problema k-server (en términos que sí importan a tu startup)

El problema k-server, según la definición de la Wikipedia del k-server problem, modela lo siguiente: tienes k servidores moviéndose por un espacio métrico (cualquier conjunto de puntos con distancias definidas entre ellos). En cada paso aparece una solicitud en algún punto, y tu algoritmo debe mover alguno de los servidores hasta esa posición, sin saber qué solicitudes vendrán después. El objetivo: minimizar la distancia total recorrida por todos los servidores.

👥 ¿Quieres ir más allá de la noticia?

En nuestra comunidad discutimos las tendencias, compartimos oportunidades y nos ayudamos entre emprendedores. Sin humo, solo acción.

👥 Unirme a la comunidad

La métrica del rendimiento es el ratio competitivo: cuánto te costó a ti, online, comparado con un adversario que conoce toda la secuencia de antemano. La cota k es el santo grial porque coincide con un límite inferior demostrado: ningún algoritmo determinista puede hacerlo mejor que k en el peor caso.

Un caso particular ya conocido desde 1985 es el paging problem (o caching): cuando todas las distancias del espacio métrico son iguales, el problema modela exactamente la decisión de qué página mantener en memoria caché. El paper clásico de Sleator y Tarjan (1985) ya demostró que para caché existe un algoritmo k-competitivo, donde k es el número de slots. Por eso el resultado de Coester et al. también impacta, de rebote, en cómo entendemos la optimalidad de las cachés y la planificación de recursos en general.

La línea de tiempo de una conjetura que no cedía

El propio paper hace un recorrido histórico riguroso por la literatura previa. Estos son los hitos que la Wikipedia del k-server problem y el paper confirman:

1988 — Manasse, McGeoch y Sleator formulan el problema y demuestran que todo algoritmo determinista tiene ratio competitivo de al menos k. También prueban que la cota es ajustada para k = 2.
1990 — Fiat, Rabani y Ravid demuestran que existe un algoritmo con ratio competitivo finito para cualquier k constante y cualquier métrica (el ratio era exponencial en k).
1991 — Marek Chrobak y Lawrence Larmore prueban la conjetura para métricas árbol (tree metrics).
1995 — Elias Koutsoupias y Christos Papadimitriou demuestran que el WFA es (2k − 1)-competitivo en métricas generales. Era el mejor bound superior hasta ahora.
2000 — Yair Bartal y Elias Koutsoupias confirman la cota k para líneas, estrellas ponderadas y métricas de k + 2 puntos.
2017 — James R. Lee anuncia un avance en la versión randomizada; el paper fue retractado posteriormente, según la Wikipedia.
2022/2023 — Sébastien Bubeck, Christian Coester y Yuval Rabani refutan la versión randomizada de la conjetura (que preguntaba si existe un algoritmo randomizado O(log k)-competitivo). El paper The Randomized k-Server Conjecture Is False! apareció en STOC 2023.
Septiembre de 2026 — Coester, Koutsoupias y Zbysiński cierran la versión determinista.

Cómo funciona la prueba, en una sola pasada

El paper no requiere inventar un nuevo algoritmo: confirma que el WFA, introducido por Chrobak y Larmore en 1991 y propuesto de forma independiente por Karloff y por McGeoch y Sleator, ya era el algoritmo correcto. La pieza que faltaba era la función potencial que midiera la amortización correcta.

La intuición técnica, según el propio paper:

El work function (función de trabajo) lleva el coste óptimo offline para servir las primeras solicitudes y terminar en cada configuración posible. El WFA escoge, en cada paso, la configuración que minimiza ese work function más el coste de moverse hasta ella.
Los autores codifican el work function como una matriz algebraica: cada valor del work function corresponde al determinante de k columnas de esa matriz. Cuando llega una solicitud, la representación se actualiza mediante un cambio de base y un reemplazo de fila.
La función potencial se define sobre una matriz más grande (el cuadrado simétrico de la original), donde cada entrada es un par de coordenadas de la matriz original. Esa estructura permite demostrar que el incremento del potencial en cada paso paga exactamente el coste extendido de servir la solicitud.

En el paper lo resumen así: la recurrencia min-plus del work function se traduce a sumas y productos de expresiones formales, y los determinantes de k columnas codifican el coste mínimo de cada configuración. La elegancia está en que las matemáticas de los valuated matroids (un concepto de Dress y Wenzel de 1992) encajan exactamente con la quasiconvexidad que el WFA necesita — una conexión que no se había explotado antes para acotar la competitividad.

Qué significa esto para tu startup

Puede sonar abstracto, pero el resultado toca tres palancas que cualquier founder tech usa — aunque no lo sepa.

Cachés y CDNs. El paging problem es el caso particular uniforme del k-server, y la cota k ya se sabía ajustada. Lo que cambia ahora es que tenemos un único marco teórico (el WFA) que justifica la optimalidad en cachés, balanceo de carga geográfico y planificación de recursos en cualquier topología, no solo en árboles o líneas. Si tu producto asigna workers, réplicas o particiones a demanda, estás usando heurísticas que el WFA acota formalmente.
Sistemas dinámicos y logística. El k-taxi problem, el stochastic k-server (modelo de Uber según un paper de 2017 referenciado en el survey) y el layered graph traversal se analizan con las mismas herramientas. Confirmar la conjetura abre la puerta a algoritmos k-competitivos en esos problemas derivados sin tener que reinventar la teoría.
Planificación bajo incertidumbre. El marco de competitive analysis se usa en autoservicio cloud, gestión de energía en datacenters y diseño de CDNs. La cota ajustada de k permite presupuestar capacidad con la garantía de que ningún algoritmo online puede mejorar ese factor — útil para fijación de precios y SLOs.

Acciones concretas que podés implementar esta semana:

Audita las cachés de tu producto. Si usas Redis, Memcached o caché de aplicación, la decisión de qué clave evictar es una variante de paging. La prueba de que el WFA es k-competitivo da una cota teórica contra la que comparar tu política LRU/LFU: medí el miss ratio real y contrastalo con la cota inferior para detectar sobreingeniería.
Modela la asignación de recursos como k-server. Si tu sistema asigna «k» workers a regiones o trabajos, y la solicitud es «atender este job en este nodo», podés formalizar el problema con la misma matemática. Hay implementaciones de referencia del WFA en la literatura de online algorithms; no necesitás reescribir tu scheduler, pero sí podés usarlo como benchmark para políticas nuevas.
Usalo como narrativa inversora. Contar que tu plataforma de logística o edge computing se apoya en el primer algoritmo con cota óptima demostrada en 38 años es una línea potente para un pitch a un fondo técnico. Koutsoupias, además, es uno de los autores — nombrar a un referente del campo en el deck suma credibilidad.

El detalle que importa a quien construye con IA

Los autores reconocen en los agradecimientos del paper que la prueba se gestó en colaboración con modelos de IA: mencionan discusiones con ChatGPT 5.5 Pro y Gemini 3.1 Pro, y que ChatGPT 6 Astra derivó posteriormente una prueba algebraica de correctitud para k arbitrario. El paper final es una adaptación de esa demostración.

Para founders que evalúan dónde la IA acelera investigación seria — y dónde no — el caso es interesante: la prueba la diseñaron los autores, pero los modelos ayudaron a reformular la función potencial de forma más simétrica y a generalizar la verificación. Coester está financiado por el ERC (proyecto CCOO, 101165139), Zbysiński por el EPSRC (EP/Z534870/1), y la verificación usó la facility Advanced Research Computing (ARC) de la Universidad de Oxford. Koutsoupias dedica el trabajo a Amos Fiat, Anna Karlin y Christos Papadimitriou, tres nombres históricos del área.

La historia humana detrás es la de un problema que sobrevivió a varias generaciones de investigadores. En 1995, cuando Koutsoupias demostró la cota (2k − 1) junto a Papadimitriou, faltaban 31 años para cerrar la conjetura. El propio Koutsoupias es coautor de la prueba final — un cierre raro en matemáticas, donde el que dejó el problema a medio resolver firma la solución.