  In this paper, we propose and study a new semi-random model for graph
partitioning problems. We believe that it captures many properties of
real--world instances. The model is more flexible than the semi-random model of
Feige and Kilian and planted random model of Bui, Chaudhuri, Leighton and
Sipser.
  We develop a general framework for solving semi-random instances and apply it
to several problems of interest. We present constant factor bi-criteria
approximation algorithms for semi-random instances of the Balanced Cut,
Multicut, Min Uncut, Sparsest Cut and Small Set Expansion problems. We also
show how to almost recover the optimal solution if the instance satisfies an
additional expanding condition. Our algorithms work in a wider range of
parameters than most algorithms for previously studied random and semi-random
models.
  Additionally, we study a new planted algebraic expander model and develop
constant factor bi-criteria approximation algorithms for graph partitioning
problems in this model.
