Layout of random circulant graphs

A circulant graph H is defined on the set of vertices V=\left{ 1,\ldots,n\right} and edges E=\left{ \left(i,j\right):\left|i-j\right|\equiv s\left($\text{mod}$n\right),s\in S\right} , where S\subseteq\left{ 1,\ldots,\lceil\frac{n-1}{2}\rceil\right} . A random circulant graph results from deleting edges of H with probability 1-p. We provide a polynomial time algorithm that approximates the solution to the minimum linear arrangement problem for random circulant graphs. We then bound the error of the approximation with high probability.