This talk will show that many of these problems (including MAX-CUT, MAX-3SAT, MIN-BISECTION, MIN-LINEAR- ARRANGEMENT) are easy to approximate if the problem instance is ``dense." For instance, a graph on n vertices is dense if every vertex has degree O(n).
Some of the above results rely upon a new randomized rounding procedure for the assignment (or bipartite matching) problem, which is of independent interest.
(Based upon two papers, one joint work with D. Karger and M. Karpinski; the other with A. Frieze and H. Kaplan.)