k-Vac

k-Vac Title Slide
The Problem
Why This Works Well
What Is The WFA Algorithm
Who is it For/Business Model
Why Standard Approaches Fail
38-year-old Problem Recently Solved: The k-server Conjecture
Empirical Evidence
Empirical Evidence

Inspiration

In September 2026, researchers here at Oxford proved the k-server conjecture is true. It had been open for 38 years and is widely seen as one of the most important problems in online algorithms. It says that a simple algorithm, the work function algorithm (WFA), is never more than k times worse than a perfect offline algorithm which knows every future request, however unpredictable the requests are.

We asked a practical question: where in the real world does this show up? Airport cleaning robots are a direct match. Spills appear without warning, robots must respond immediately, and every metre they drive is time wasted. Greedy dispatch (send the nearest robot) has no limit on how much time is lost. We wanted to put a brand-new result into a real setting.

What it does

k-Vac is dispatch software for airport cleaning robots with a proven limit on wasted time, however unpredictable the spills.

A web page shows a floor plan of an airport terminal, with robots running our WFA algorithm in green and robots running a greedy nearest-robot algorithm in grey, both handling the same spills. Areas where spills are more likely, such as the food court, are modelled with a scalar field and shown as a heatmap. Spills are generated at random in proportion to that field. Robots move to spills in the order they appear. A live table compares the distance each fleet has travelled with the offline optimum, the best a planner could do if it knew every spill in advance. Sliders control the number of robots, the number of hot areas, and the heatmap, so you can test different scenarios.

How we built it

The algorithm: the work function algorithm uses dynamic programming. It scores, for every possible arrangement of robots, the cheapest way a planner with hindsight could have served all the spills so far and ended up in that arrangement. On each new spill it makes the move that keeps that score lowest. So it behaves as if it predicts the future, without making any explicit prediction. The k-bound holds whatever the spill pattern, and nothing equivalent holds for greedy.

The stack:

React frontend, drawing the floor plan, heatmap, robots and live comparison table Python backend, implementing WFA, the greedy baseline and the offline optimum FastAPI, exposing the backend so the frontend can connect to it Claude, used to help build parts of the code and interface

Challenges we ran into

Understanding the conjecture itself. It is a recent research result, and we had to work out what it does and does not say. Working out how to apply it to a real problem, including mapping robots to servers and spills to requests on a floor plan. Understanding how WFA actually works, and making sure our implementation matches the maths. Computation cost. WFA tracks every arrangement of robots, so it slows as robots are added. We saw this at five robots.

Accomplishments that we're proud of

Taking a brand-new theoretical result, only weeks old, and turning it into a working, visual demo in a hackathon weekend. Showing the gap against greedy on screen, with the offline optimum as an honest benchmark. A team that can explain the maths behind the algorithm, not only show the demo.

What we learned

How online algorithms and competitive analysis work, including why “never more than k times optimal” is a different kind of guarantee from “usually faster”. How to read and apply a research paper, and how to explain it to people who haven’t seen it. Dynamic programming and the work function in practice. Building and benchmarking a simulation, and wiring a React frontend to a Python backend. Splitting work across a team and keeping it consistent under time pressure.

What's next for k-Vac

Realism: adding battery, charging, spill priorities and cleaning time. Scale: making WFA faster for larger fleets and bigger maps, for example with approximations. Real data: replacing synthetic spills with real incident data. Integration: an API so existing robot fleets can use it. Business: per-robot and per-site subscriptions for contractors and operators, and OEM licensing for robot makers