An Intractable Problem?

In the most technical sense of the term, some forms of social network optimization are intractable, while others are not.  One famous problem with explicit social implications is the stable marriage problem.  It has been shown that one version of this problem is of polynomial time with respect to N, the number of individuals of each sex to be matched.  Technically, a problem solvable in polynomial time is tractable. In fact, the Gale-Shapley algorithm depends on only the square of the number of points.

However, the number of marriageable people in the world at any one time is probably in the hundreds of millions.  One experimental implementaton of the algorithm, working on N = 100, one hundred men and 0ne hundred woman, took about 8 seconds on a typical personal computer.  To create 1,000 couples — ten times as many — would take not just 80 seconds, but 800 seconds — one hundred times as many.  Matching hundred of millions of couples is intractable in practice, so though not in theory, because N is just too large to handle.

A stable marriage problem solving algorithm has been used for many purposes, such as matching residents to hospitals, or students to dorm rooms, but none have been large problems, involving vast numbers of people.

Some problems superficially like the stable marriage problem are much harder to solve. The assignment problem, or weighted matching problem, depends not on the square but on the cube of the number of individuals.  Both are easy problems, though — of polynomial complexity.  Variations of matching problems have been defined which have exponential or even factorial running times.  Both are intractable in the most technical sense.

For example, there are 4950 different ways of picking couples from 100 people. This number is linear, so there are 49,500 ways of picking couples from 1000 people.  On the other hand, picking more people is a more difficult problem.  I have written a lot about schools.  How many different ways are there to divide 100 students into 5 classes of 20? There are 535,983,370,403,809,682,970 different ways.  For forming pairs, the problem is linear in the size of the population. However, the problem is factorial in the size of the groups.

Dividing 100 students into classes of 20 is not a very abstract problem.  It is the kind of problem which school administrators and teachers face regularly.  Solving it is an intractable optimization problem.  It matters, too.  Students are much more likely to interact with people in the same class.

Leave a Reply

Your email address will not be published. Required fields are marked *