BAP: Lecture 10 (Mar 14, 2002)

• latex,
• postscript, and
• pdf

• Introduced a smoothed model for bandwidth, and proved that it was weaker than the monotone adversary model. We also observed that Turner's theorem holds for the monotone adversary model, so it holds for the smoothed model.
  Papers on the monotone adversary model include:

  • @article{ blum95coloring,
        author = "Avrim Blum and Joel Spencer",
        title = "Coloring Random and Semi-Random k-Colorable Graphs",
        journal = "J. Algorithms",
        volume = "19",
        number = "2",
        pages = "204-234",
        year = "1995",
        url = "citeseer.nj.nec.com/blum95coloring.html" }
    

  • "Heuristics for Semirandom Graph Problems" by Uri Feige and Joe Kilian. To appear in Journal of Computer and System Sciences. A preliminary version, named "Heuristics for finding large independent sets, with applications to coloring semi-random graphs", appeared in the Proceedings of 39th FOCS, 674--683, 1998. Available at Uri Feige's homepage.
  • "Improved performance guarantees for bandwidth minimization heuristics", by Uri Feige and R. Krauthgamer . Unpublished manuscript, November 1998. Available at Robert Krauthgamer's homepage.
• We discussed algorithms for bisection in the planted bisection model. Papers mentioned included:

  • @article{ condon01algorithms,
        author = "Anne Condon and Richard M. Karp",
        title = "Algorithms for graph partitioning on the planted partition model",
        journal = "Random Structures and Algorithms",
        volume = "18",
        number = "2",
        pages = "116-140",
        year = "2001",
        url = "citeseer.nj.nec.com/article/condon99algorithms.html" }
    

  • "Eigenvalues and graph bisection: an average-case analysis", by Ravi Boppana. Appeared in the Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pages 280-285, IEEE Computer Society Press, 1987.
  • Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning, D. S. Johnson, C. R. Aragon, L. A. McGeoch and C. Shevon, Operations Research, 37:6 (1989), 865-892. (available at JSTOR).
• We then examined Frank McSherry's analysis of a spectral partitioning algorithm for the planted bisection model. The paper is: "Spectral Partitioning of Random Graphs", and it appeared in STOC '01.

n = 100;
a = [rand(n) < .2, rand(n) < .1; rand(n) < .1, rand(n) < .2];
a = a + a';
spy(a)
p = randperm(200);
b = a(p,p);
spy(b)
[v,d] = eigs(b,4);

Iteration 10: a few Ritz values of the 20-by-20 matrix:
  -13.5374
   14.5138
   21.7683
   59.6353

d

d =

   59.6353         0         0         0
         0   21.7683         0         0
         0         0   14.5138         0
         0         0         0  -13.5374

[w,perm] = sort(v(:,2));
plot(w)
c = b(perm,perm);
spy(c)
figure(2)
plot(p(perm))
pp = p(perm);

sort(pp(1:100))

ans =

  Columns 1 through 14 

   101   102   103   104   105   106   107   108   109   110   111   112   113   114

  Columns 15 through 28 

   115   116   117   118   119   120   121   122   123   124   125   126   127   128

  Columns 29 through 42 

   129   130   131   132   133   134   135   136   137   138   139   140   141   142

  Columns 43 through 56 

   143   144   145   146   147   148   149   150   151   152   153   154   155   156

  Columns 57 through 70 

   157   158   159   160   161   162   163   164   165   166   167   168   169   170

  Columns 71 through 84 

   171   172   173   174   175   176   177   178   179   180   181   182   183   184

  Columns 85 through 98 

   185   186   187   188   189   190   191   192   193   194   195   196   197   198

  Columns 99 through 100 

   199   200

plot(w)
diary off