Assignment polytope

From Glossary

Jump to: navigation, search

The assignment polytope is

\left\{ x \in \mathbb{R}^{n^2} : x \ge 0, \; \sum_i x_{i,j} = 1 \mbox{ for } j = 1, 2, \ldots, n, \;
\sum_j x_{i,j} = 1 \mbox{ for } i =  1, 2, \ldots, n \right\}.

The name originates from an interpretation of its extreme points in the assignment problem. If LaTeX: x_{i,j} = 1, assign person LaTeX: i to task LaTeX: j. Each extreme point has the property that each element of LaTeX: x is 0 or 1. The sums describing the polytope require that each row (LaTeX: i) and each column (LaTeX: j) has exactly one 1 in it. This means every person is assigned to some task, and every task is assigned to be done by one person. The polytope is also the set of doubly stochastic matrices, whose extreme points are the permutation matrices.

Personal tools