The above examples illustrate the first two types of matrices. Note the right matrix of each example. Both are doubly stochastic and (0,1). Thus, both are examples of permutation matrices. In return, permutation matrices are a special case of the previous types. Notice how forcing both properties result in being exactly one '1' in each row and column.

Example 3 Two dimensional polyhedra.

$\epsfig{file=polygons.eps,scale=0.7}$

The preceding figures are simple polyhedrons. The first three are convex. The last is not convex because if you draw a line between two of the endpoints the line will exist outside the polyhedron. Since the first three figures are convex polyhedron, the compact set of points forming the polyhedron constructs polytopes.

Now with all the necessary terminology defined, the Birkhoff Polytope can be formally introduced.

Definition 7 A Birkhoff Polytope of size

, written as $\Omega _n$ , is a compact convex polyhedron of all

nonnegative doubly stochastic matrices with the following properties:

The vertices of the polytope of size are the x permutation matrices.
The dimension of the polytope of size is . [Brualdi and Gibson, 1977]

From a geometric perspective the Birkhoff Polytope is a type of convex polyhedra, like a pentagon and a hexagon are types of convex polygons. Since the set of vertices of the polytope is the set of permutation matrices, the number of vertices is . This means that the size of the Birkhoff Polytope grows very fast. As an illustration, $\Omega _{5}$ has vertices, while $\Omega _{15}$ has vertices. While the permutation matrices represent just the vertices of $\Omega _n$ , all nonnegative doubly stochastic matrices compose the entire polytope. The non-permutation matrices will be discussed further in polytope relations. Use a ref tag here

Vertex Representation

While the permutation matrix of size

is the most common way to think of a vertex, elements of the symmetric group of degree

, from Abstract Algebra, can be used as well. In the matrix representation of the vertex, each

is found in a row

and a column

. While in the symmetric group representation, the vertex is represented by a function that maps each

to a unique

called a permutation. By the properties of the symmetric group, each permutation is automorphic, meaning there is a 1-1 and onto mapping of

Example 4 Two ways to represent a vertex.

$\begin{displaymath} \left[ \begin{array}{cccc} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & ... ...{cccc} 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 \end{array} \right) \end{displaymath}$

Birkhoff Polytopes

Polytopes have the ordinary properties of polyhedra. They are composed of vertices, edges, planes, and higher dimensional objects. These objects composing the polytopes are classified as faces.

Definition 8 A face is the intersection of a polytope and hyperplane for which the polytope is entirely contained in one of the two half spaces determined by the hyperplane (

-dimensional plane). [Ziegler, 1995]

Polytopes can intersect a hyperplane at a single point, across a line segment, and so forth. A single point is a -dimensional object and thus a vertex is a -dimensional face. With the same logic, edges are -dimensional faces and planes are -dimensional faces. A facet is -dimensional face of an -dimensional polytope. With Birkhoff Polytopes, faces have a matrix representation in addition. There is a subset of all x matrices that forms a correspondence to the set of faces of $\Omega _n$ . To define the subset that corresponds to the set of faces of $\Omega _n$ , a few more ideas need to be introduced.

Total Support and the Permanent

What are they?

Definition 9 An

nonzero

matrix $B = [b_{ij}]$ is said to have total support, with the property that for $1 \leq r,s \leq n \ni b_{rs}=1$ , there exists at least one one permutation matrix $P = [p_{ij}]$ where $p_{rs}=1$ and $\forall u,v \ni 1 \leq u,v \leq n$ , $p_{uv} \leq b_{uv}$ . [Brualdi and Gibson, 1977]

A matrix with total support is a matrix that can be decomposed into a set of permutation matrices. The number of permutation matrices that are decomposed from any matrix is called the permanent.

Definition 10 The permanent of the (0,1) matrix with total support, A, is defined by [Brualdi and Gibson, 1977]

$\begin{displaymath} per A = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i \sigma(i)} \end{displaymath}$

The permanent, though complex looking, performs a simple and elegant procedure. The function takes the sum of a product for every element of , or for each vertex of $\Omega _n$ . The product is taken of selected elements from the matrix. The rows of the matrix are selected in order, 1 through . The columns are determined from $\sigma(i)$ , which will return the column in which row has a 1 in the matrix representation of $\sigma$ . This means that the permanent is comparing each vertex of the polytope to the matrix. The product taken will either be 0 or 1, because is a matrix. Furthermore, the product is one when the 1s in the permutation matrix of $\sigma$ are in matrix . Otherwise, the product is 0. Thus, the sum returned is the number of vertices contained in the matrix .

Defining the Subset

The subset of

-matrix is defined as the set of

-matrix with total support. This is the subset that forms the

correspondence with the faces of $\Omega _n$ . A matrix

has total support then it corresponds to the face of

denoted by $\mathcal{F}(A)$ . The following theorem proves the correspondence just stated.

Theorem 3.1 Let $P_1,\ldots,P_t$ be distinct x permutations matrices. Let $A=[a_{ij}]$ be the x -matrix such that $a_{ij}=1$ if and only if the -entry of at least one of the 's is 1. Then has total support and $\mathcal{F}(A)$ is the smallest face of $\Omega _n$ which contains the vertices $P_1,\ldots,P_t$ . Moreover, $P_1,\ldots,P_t$ are the vertices of a face $\Omega _n$ if and only if [Brualdi and Gibson, 1977].
$\begin{proof} % latex2html id marker 386 From the definition of $A$, $A$ has ... ... are the vertices of $\mathcal{F}(A)$ if and only if $per A = t$. \end{proof}$

Example 5 A face and its vertices.

$\begin{displaymath} \left[ \begin{array}{cccc} 1 & 0 & 0 & 1\\ 0 & 1 & 1 & ... ...& 0\\ 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 \end{array} \right] \end{displaymath}$

Give example of a face and its vertices

Consider an x matrix filled with all ones, call it . Every permutation matrix is found in . The permanent of supports the claim as the function returns a value of . This case turns out to be special. is the face corresponding the whole polytope, $\Omega _n$ . This face is generally referred to as $\Omega _n$ . The permanent function is powerful and has several uses beyond the scope of this research.

Edges

With the ability to determine the vertices in a face, it would be nice to determine which vertices are connected through an edge. This is beneficial in understanding what type of faces can be constructed and in visualizing the two and three dimensional faces of the polytope. Furthermore, it will help in understanding how $\Omega _n$ relates to $\Omega _{n+1}$ . As it turns out, it is possible to determine which pairs of vertices are connected. Before the technique that explains how to determine edges is introduced, the idea of cycle numbers need to be introduced.

Definition 11 Let

be an

permutation matrix. Then the cycles of

are defined to be the cycles of the permutation that corresponds to

. If

is also an

permutation matrix, then the cycle number of

and

, denoted as

, equals the number of cycles of length greater than 1 of the matrix $P^{-1}Q$ . [Brualdi and Gibson, 1977]

Determining the cycle number may seem like a tedious task, when considering it in terms of matrices. Finding matrix inverses and matrix multiplication are laborious tasks. However, vertices also have permutation representations from , the symmetric group. The inverse of an element of a group is computed by reversing the mapping. The product of two elements is found by composing the two mappings. Furthermore, tracing and counting cycles is much easier because the permutation lays out the mapping.

Theorem 3.2 Let , be distinct x permutation matrices. Then $v(P,Q) \geq 1$ with equality (meaning ) if and only if and are the vertices of a 1-dimensional face (edge) of $\Omega _n$ [Brualdi and Gibson, 1977].
$\begin{proof} % latex2html id marker 429 Clearly $v(P,Q) \geq 1$ if $P \neq Q... ...rm}, $I$ and $Q$ are the vertices of a face if and only if $k=1$. \end{proof}$

In order to prove that the cycle number needs to be one, for the edge to exist, previous definitions are used to obtain a matrix from and , which can be simplified due to the invariance of permutations to and . Recall, that multiplying a matrix by a permutation matrix shuffles columns and rows. The picked allows the rows and columns to be shuffled to create a matrix that can represented by a direct sum ( $\oplus$ ). Each has an order of at least two, implying that the . The $per A = per RAR^{-1}$ because since the matrix is only being shuffled, ever vertex that is lost from the shuffling is replaced by a new one. , since the permanent is equivalent to product of permanents of the direct sum. In order for a face to be an edge, it must contain exactly two vertices, therefore must equal .

With this technique, it would be nice to know what the edge graphs of some of the smaller graphs looks like. This would help in visualizing the polytope and understanding the nature of it. To accomplish this, I wrote a simple that program performed the cycle number test on each pairing on vertices to obtain a graph. Figure 1. includes the graphs of $\Omega _3$ and $\Omega _4$ . Each vertex was assigned a letter, starting with and continuing until all vertices are labeled.

**Figure 1:** Edge Graphs of $\Omega _3$ and $\Omega _4$ .
$\begin{figure} % latex2html id marker 437 \begin{displaymath} \begin{array}{c... ...& 1 & 1 & 1 & 1 & 1 & 1 & 0\\ \end{array} \end{displaymath} \end{figure}$

Several observations can be gathered from the graphs. First, there exists symmetry across both diagonals of the edges graphs of the polytopes. The forward diagonal (starting in the top left corner) is expected because the graph is undirected and therefore an edge from to implies there exists an edge from to . The backward diagonal (starting in the top right corner) is an unanticipated result. In the case of $\Omega _4$ , why should edge related to . It turns out $B^{-1}V = (W^{-1}C)^T$ as a result of $\mathcal{F}(A) \cong \mathcal{F}(A^T)$ . Further observation leads to the fact that each vertex has the same number edges, meaning that the degree of each vertex is the same. This result relies on vertices being represented by elements of the .

Diameter

The edge graphs visually show that for at least small values of

, the graph of $\Omega _n$ is very dense. Looking at $\Omega _4$ , each of the 24 vertices have a degree of 20. That is about 87% of of the edges in a complete graph of the same size. A complete graph is a graph where there exists an edge for all pairings of vertices. In addition, it might be beneficial to understand the number of edges between any two points.

Definition 12 The diameter of a graph is the largest value from the minimum number of edges that must traversed to travel between each pairing of vertices. That is to say the diameter is the longest length of the shortest path of the graph. [Weisstein, 2005]

A computer program tested the diameter of Birkhoff polytopes of size 1 through 9, by generating an edge graph and utilizing a Transitive Closure algorithm [Cormen et al., 2001]. Each polytope has a diameter of 2. The method in which the diameter is calculated requires large computer resources. For instance, to find the diameter of $\Omega _9$ used over half the memory on the department sever and ran for seven days. To compute the diameter of larger Birkhoff polytopes in this manner would require more memory and much more time. Using this method, $\Omega_{20}$ would require more computational time than the age of the universe. This leads to looking for alternative methods for determining the diameter.

To gain some understanding of the diameter of the graph, the question of is the diameter of all Birkhoff polytopes 2 is addressed. Past research that Dr. Hightower and I have conducted suggested that this may be possible. To address this idea, the ratio of the degree of a vertex of $\Omega _n$ to the degree of a vertex of a complete graph $K_{n!}$ is considered. Since $\Omega _n$ has vertices the complete graph being compared must also have vertices. Graphs with a diameter of 2 are very dense, meaning that as the number of vertices increases to infinity, the number of edges will also increase to infinity. If the sequence of ratios

$\begin{displaymath} \left\{ \frac{deg(\Omega_n)}{deg(K_{n!})} \right\}_{n=1}^{\infty} \end{displaymath}$

diverges then it is possible that the diameter is 2 for all Birkhoff polytopes.

Degree of a Vertex

In order for the ratio to be useful, there needs to be formulas to determine the degree for each graph. In a complete graph, each vertex is connected to every other vertex. Therefore, if there are

vertices, then the degree of each vertex is

. As a result, $deg(K_{n!}) = n!-1$ . To determine a formula for the degree of $\Omega _n$ , it is essential to recall Thm 3.2. The theorem states that the an edge exists between two vertices when after manipulating the two vertices, there is exactly one cycle of length greater than 1. Since the the vertices form a group, the result of the manipulations results in another element from the group. This means that the calculating the degree is equivalent to counting the number of permutations with a cycle number of 1.

Consider that for the edge to exist there must be exactly one cycle of length greater than one. This implies that at least two vertices must be permuted and all vertices not permuted map to themselves. In order to count the permutations of with the given property, first select a cycle of length from 2 to , call it . For the selected cycle length, determine the number of ways of choosing which elements of the permutation to be part of the mapping, ${n\choose k}$ . Once, the cycle location is picked, the different orders of the cycle are calculated, . This means that there are ${n \choose k}(k-1)!$ elements of with a cycle length of . To consider all elements with a cycle length greater than one, gives the degree of a vertex of $\Omega _n$ . The formula follows.

$\begin{displaymath} deg(\Omega _n) = \sum_{i=2}^{n} {n \choose i}(i-1)! \end{displaymath}$

The Ratio

With formulas to determine both degrees, the ratio can provide insight into the nature of the bigger polytopes. The ratio contains several factorials, making it difficult to calculate for large numbers. In this case it would beneficial if there was a way to approximate the value. The ratio can be simplified as is shown in the following.

$\begin{displaymath} \frac {\sum_{i=2}^n {n \choose i} (i-1)!} {n! - 1} = ... ...\left( \frac{n!}{n!-1} \right) \sum_{i=2}^n \frac{1}{i(n-i)!} \end{displaymath}$

To renumber the summation to start at zero, let

$\begin{displaymath} \left( \frac{n!}{n!-1} \right) \sum_{i=2}^n \frac{1}{i(n-i)... ... \frac{n!}{n!-1} \right) \sum_{k=0}^{n-2} \frac{1}{n\cdot k!} \end{displaymath}$

Considering as

increases in size for larger polytopes, the following inequality is made.

$\begin{displaymath} \frac{deg(\Omega_n)}{deg(K_{n!})} = \left( \frac{n!}{n!-1... ...ight) \sum_{k=0}^{n-2} \frac{1}{k!} \rightarrow \frac{e}{n} \end{displaymath}$

Since $\frac{n!}{n!-1} \rightarrow 1$ , it follows easily that

$\begin{displaymath} \frac{deg(\Omega_n)}{deg(K_{n!})} \rightarrow \frac{e}{n} \end{displaymath}$

Results

Observing the approximation for large values of

shows that the polytope has a very low percentage of edges connecting the vertices. This implies that in fact the diameter is not 2 for all Birkhoff polytopes. The following table lists several sizes of

and the implications it has on ratio and number of edges in the polytope.

$\begin{displaymath} \begin{array}{c\vert cc\vert c} n & deg(\Omega _n) & deg(K... ...3 \cdot 10^{373} & 7.8866 \cdot 10^{374} & 0.014 \end{array} \end{displaymath}$

One observation noted from the chart is that though the polytopes become more sparse as the becomes large, the chart shows that the degree of each vertex is still very large number.

Assignment Problems

Preliminaries

Assignment problems belong in the class combinatorial optimization problems. The objective of these problems is to find either minimum or maximum cost for the given set of conditions. Generally, these problems assign one object to another with a given cost. Assignment problems are one of the well studied problems in mathematical programming [Akgü, 1993]. The studying and solving of assignment problems was benefited with the creation of Linear Programming.

Types

There are several types of Assignment problems, one of these being the Linear Assignment Problem. This can be referred to as an agent/task problem, where there a

tasks and

agents. Each agent can complete each task with a cost. Examples of the cost could be time, money, or resources. The costs are stored in a cost matrix where the rows represent the agents and the columns represent the tasks. The goal is to minimize the cost needed to assign the problems.

Quadratic assignment problems are another member of this family. There are facilities and locations. For each pair of locations there is a distance and cost associated. An example of the cost could be the money or time needed to transport goods between factories. The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding costs [Kabel, 1997].

Other types of Assignment Problems, which will not be talked about any further include: Multiple Assignment Problems which allow for there to be more tasks than agents and 3D Linear Assignment Problems which add another constraint to traditional agent/task situation. Many members of the family of problems are variations of other problems. The Multiple Assignment is an example of this.

Network Simplex Method

The network simplex method is a special case of the simplex method when dealing with network flow based problems. The simplex method and network simplex method model that problems in the form of $A\cdot x=B$ . The network simplex method exploits characteristics of network flow based problems to allow for a simplification of the problem [Chvátal, 1983]. The Network Simplex method for LAPs has been shown to run in polynomial time [Akgü, 1993], while in general the method runs in non-polynomial time.

Birkhoff Polytopes and Linear Assignment Problem

Recall that that LAP assigns each task to an agent. To represent a possible assignment with an x matrix, place a 1 where agent is assigned to task and place 0s everywhere else. The matrix created is identical to a permutation matrix from $\Omega _n$ . The polytope represents all possible ways to assign the tasks. However, if the assignment matrix is not representing a vertex then the assignments are split among different agents, thus making it not a feasible solution. Only the vertices are feasible solutions, reiterating each agent being assigned one task.

Network Simplex Method

The network simplex method utilizes the permutation matrices in the fashion as described above. The initialization of the method starts by picking a permutation matrix, say the identity. The network simplex method assigns a variable to each element of the matrix. This is illustrated below.

$\begin{displaymath} \left[ \begin{array}{ccc} x_{11} & x_{12} & x_{13} \\ x_... ..._{12}, x_{13}, x_{21}, x_{23}, x_{31}, x_{32} = 0 \end{array} \end{displaymath}$

With the permutation selected, a set of equations need to be set up to use the algorithm. For each of the row set, let the left side of the equation equal the element from the permutation. Since the matrix is doubly stochastic, the right side of the equation is 1 subtracted by the other elements in the row. Now two other elements need to be selected. As before these elements form equations as stated before, but this time with columns instead of rows. However, any elements that are on the left hand side of the system cannot be on the right and must be substituted out of the right hand side.

$\begin{displaymath} \begin{array}{ccccccccccc} x_{11} & = & 1 & & & & - x_{21}... ...0 & & & & & & - x_{23} & + x_{31} & + x_{32} \\ \end{array} \end{displaymath}$

One nice result of initializing the matrices is that only the equations corresponding to the permutation have a 1 in them. The heart of the network simplex is pivoting. Pivoting involves swapping a variable on the left with a negative variable on the right and then substituting. There are two types of pivots: degenerate and non-degenerate. Degenerate pivots occur when swaps are made on an equation with a 0 constant, while non-degenerate pivots occur when swaps are made on equations with a 1 constant. When non-degenerate pivots occur a change in the permutation matrix being represented occurs. Recall, the equations with ones represent the permutation, by pivoting one of these equations, the permutation being considered is changed.

It turns out that the permutations that can be pivoted to are those with edges connecting the vertices of the permutations. The network simplex method optimizes the problem by traversing the Birkhoff polytope of the problem.

Polytopes and Quadratic Assignment Problems

The Quadratic Assignment Problem can also be modeled by polytopes [Kabel, 1997]. However, for a QAP of size

, $\Omega _n$ is embedded into it. Though the vertices are embedded into the QAP polytope, not all of edges are incorporated in the QAP. Though all of the vertices are possible solutions for the QAP, there are more vertices in the polytope than just the integer value solutions. The extra solutions are matrices that are double stochastic but not

. This increase the complexity of finding a minimal solution. With further research it may be possible to utilize the the Birkhoff polytope in discovering improvements for algorithms to solve Quadratic Assignment Problems.

Conclusion

This semester has proved to be a challenging and rewarding semester. I have read from from a variety of sources including journal articles, books, and a thesis. In order to understand several of the readings I had to learn significant background information. The research led to the understanding of structure of Birkhoff Polytopes and their relations to assignment problems.

Where to go next

Though, I have accomplished several goals in this project, there are more questions that I feel are worth looking at.

Is there a function that models the diameter of $\Omega _n$ ?
If such a function exists, can it be used to create a better performing algorithm?
What is the structure and what are the properties of the polytopes of the other assignment problems?
What are the similarities of the polytopes of different assignment problems? Is there a common structure?

Appendix

Birkhoff.java

The program is designed to count the edges, calculate the diameter, and generate the vertices of $\Omega _n$ .

public class Birkhoff {
   int FACTN;
   int N;
   int C;
   int E;
   int[][] Sn;
   byte[][][] verticies;
   byte[][] G;

   int factorial(int n) {
      int fact=1;
      for(int i=2; i<=n; i++) fact*=i;
      return fact;
   }

   void permute(int list[], int n, int prelist[], int m) {
      if(n>0){
         int[] sublist = new int[n-1];
         for(int i=0; i<n; i++) {
            int k=0;
            for(int j=0; j<n; j++)
               if(i != j) sublist[k++] = list[j];
            prelist[m] = list[i];
            permute(sublist, n-1, prelist, m+1);
         }
      } else {
         for(int i=0; i<N; i++)
            Sn[C][i] = prelist[i];
         C++;
      }
   }

   void combine(int sublist[], int prelist[], int n, int m, int r){
      if(n == r) {
         if(n==2) {
            //Edge Test
            cyclenumber(prelist[0], prelist[1]);
         } else {
      } else {
         for(int i=m; i<sublist.length; i++) {
            prelist[n] = sublist[i];
            combine(sublist, prelist, n+1, i+1, r);
         }
      }
   }

	void cyclenumber (int p, int q) {
      //First print cycles for each permutation
      int[] pT = new int[N];
      for(int i=0; i<N; i++) {
         int image = Sn[p][i];
         pT[image] = i;
      }
      //Q
      int[] Q = new int[N];
      for(int i=0; i<N; i++) Q[i] = Sn[q][i];
      //Compose cycles
      int[] pTq = new int[N];
      for(int i=0; i<N; i++) pTq[i] = Q[pT[i]];

      //Check Cycles
      int v;
      int ct=0;

      for(int i=0; i<N; i++) {
         v=0;
          if(pTq[i] != -1) {
            int next=i;
            int prev;
            do {
               v++;
               prev = next;
               next = pTq[next];
               pTq[prev] = -1;

            } while(next != i);
            if(v > 1) ct++;
          }
      }
      if(ct == 1) {
         if(!(G[p][q] == 1 | G[q][p] ==1) ) E++;
         G[p][q] = G[q][p] = 1;
      }
   }
   void run() {
      N=8;
      FACTN=factorial(N);
      C=0;
      int[] list = new int[N];
      int[] prelist = new int[N];
      Sn = new int[FACTN][N];
      verticies= new byte[FACTN][N][N];
      G = new byte[FACTN][FACTN];

      for(int i=0; i<FACTN; i++) {
         for(int j=0; j<FACTN; j++) G[i][j] = 50;
         G[i][i] = 0;
      }
      for(int i=0; i<N; i++) list[i] = i;

      //Create the Symertic Group
      permute(list, N, prelist, 0);

      list = new int[FACTN];
      for(int i=0; i<FACTN; i++) list[i] = i;

      E=0;
      for(int i=2; i<3; i++){
         prelist = new int[i];
         //Combine (n!,2) -> (n!,n-1)
         combine(list, prelist, 0, 0, i);
      }
      System.out.println("Edge Count - " + E);

      byte max = 0;
      for(int i=0; i<FACTN; i++)
         for(int j=0; j<FACTN; j++)
            if(max < G[i][j]) max = G[i][j];
      System.out.println("Degree - " +max);
   }

   public static void main(String args[]) {
      combinations birkoff = new combinations();
      birkoff.run();
   }

   void transitive_closure() {
      int k,i,j;
      for(k=FACTN-1; k>=0; k--) {
         for(i=FACTN-1; i>=0; i--)
            for(j=FACTN-1; j>=0; j--)
               if((G[i][j] > G[i][k] + G[k][j] ) )
                  G[i][j] = (byte)(G[i][k] + G[k][j]);

         if(k%1000 == 0)
         System.out.print(" " + k + " of " + FACTN);
      }
   }

   void degree() {
      for(int i=0; i<FACTN; i++) {
         int sum = 0;
         for(int j=0; j<FACTN; j++)
            if(G[i][j] == 1) sum ++;
         System.out.println("Degree of " + i +":" + sum);
      }
   }
   
}

Bibliography

Akgü, 1993: Akgü, M. (1993).
A Genuinely Polynomial Primal Simplex Algorithm for the Assignment Problem.
Discrete Apllied Mathematics, 22:93-115.
Brualdi and Gibson, 1977: Brualdi, R. A. and Gibson, P. M. (1977).
Convex Polyhedra of Doubly Stochastic Matricies. I. Applications of the Permanent Function.
Journal of Combinatorial Theory, Series A, 22:194-230.
Chvátal, 1983: Chvátal, V. (1983).
Linear Programming.
Freeman.
Cormen et al., 2001: Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001).
Introduction to Algorithms, Second Edition.
The MIT Press.
Grunbaum, 2003: Grunbaum, B. (2003).
Convex Polytopes, volume 221 of Graduate Texts in Mathematics.
Springer.
Kabel, 1997: Kabel, V. (1997).
Polyhedral Combinatorics of the Quadratic Assignment Problem.
PhD thesis, Universität zu Köln.
Matovsek, 2002: Matovsek, J. (2002).
Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics.
Springer.
Weisstein, 2005: Weisstein, E. (2005).
MathWorld - A Wolfram Web Resource.
http://mathworld.wolfram.com.
Ziegler, 1995: Ziegler, G. M. (1995).
Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics.
Springer.

About this document ...

Combinatorial Geometry of Birkhoff Polytopes

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

The command line arguments were:
latex2html -split +0 -white final.tex

The translation was initiated by Zach Jones on 2006-03-19

Zach Jones 2006-03-19

Combinatorial Geometry of Birkhoff Polytopes

Introduction

What is Covered

Motivation

Birkhoff Polytope Preliminaries

What is a Birkhoff Polytope

Vertex Representation

Birkhoff Polytopes

Total Support and the Permanent

What are they?

Defining the Subset

Edges

Diameter

Degree of a Vertex

The Ratio

Results

Assignment Problems

Preliminaries

Types

Network Simplex Method

Birkhoff Polytopes and Linear Assignment Problem

Network Simplex Method

Polytopes and Quadratic Assignment Problems

Conclusion

Where to go next

Appendix

Birkhoff.java

Bibliography

About this document ...