Recommendable! It took 15 years to refine the algorithm.
"... You can always make [two or more] teams [of extremely different individuals] surprisingly even, according to researchers studying combinatorial discrepancy theory.
Discrepancy theory is a branch of mathematics concerned with allocating resources as evenly as possible. ...
In the early 1980s, the mathematician János Komlós came up with a counterintuitive [conjecture]. He [predicted] that no matter how many objects (your players) or dimensions (... categories [or dimensions, attributes]) you consider, the discrepancy — which you can quantify — will never exceed a constant amount. There will always be a way to divide the teams with a discrepancy below that exact amount. ...
If the Komlós conjecture is true, it could unlock answers to many other problems, both within discrepancy theory and in fields like operations research. ...
Then, in fall 2025, [researchers] announced the first major advance on the problem(opens a new tab) in nearly 30 years. They found a limit that changes so slowly with the dimension that it is only a hair away from constant, even with an astronomical number of dimensions. ...
The Komlós conjecture imagines each person (or object) as an arrow of length 1 called a unit vector. This vector is defined by a list of coordinates, where each coordinate measures how much of a particular attribute that person has. ...
Now assign each vector to a team. If you put a vector in Team A, leave its coordinates alone. If you put it in Team B, multiply each of its coordinates by −1. (This flips the vector around.) ...
If you’re able to make a perfect split, dividing people into two teams so that each team has an equal ..., then all of these vectors should add up to zero. Perfect harmony.
But perfection usually isn’t possible. So the question becomes: How close to zero can you get? ...
Consider one naïve strategy: Simply assign vectors to teams at random. This leads to a discrepancy that skyrockets as the number of vectors, N, increases.
In 1985, Joel Spencer found a better bound, capping discrepancy below the logarithm of N;
in 1998, Wojciech Banaszczyk improved the bound to 
, which can also be written as log(N)½. Both were meaningful strides, but the amount of imbalance still grew as the number of vectors did. Komlós’ constant felt out of reach. ...
, which can also be written as log(N)½. Both were meaningful strides, but the amount of imbalance still grew as the number of vectors did. Komlós’ constant felt out of reach. ...
In 2010, he came up with an idea for an algorithm(opens a new tab). He started by splitting each vector in half. ..."
Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk (preprint, open access)
From the abstract
No comments:
Post a Comment