The Maximum Cut Problem

The maximum cut problem (MAX-CUT) is one of the fundamental problems in combinatorial optimization. This chapter discusses the complexity of the MAX-CUT problem and of certain cases where the problem can be solved in polynomial time. It presents some applications of the MAXCUT problem. The chapter discusses the cut polytope. The chapter introduces certain classes of facets of this polyhedron and it studies their separation problems. The chapter describes some branch-and-cut algorithms for solving the MAX-CUT problem. It devotes to studying the MAX-CUT problem using semi-definite programming. The chapter introduces certain applications of the cuts cone. It also introduces some approximation methods for the MAX-CUT problem, both with and without guarantees. It also discusses the polyhedral aspect of some problems that are related to the MAX-CUT problem.