New Convex Relaxations for the Maximum Cut and VLSI Layout Problems

摘要: It is well known that many of the optimization problems which arise in applications are “hard”, usually means they NP-hard. Hence much research has been devoted to finding “good” relaxations for these hard problems. Usually a relaxation one can be solved (either exactly or within prescribed numerical tolerance) polynomial-time. Nesterov and Nemirovskii showed by this criterion, convex good relaxations. This thesis presents new two such problems, namely Maximum-Cut (Max-Cut) problem VLSI (Very Large Scale Integration electronic circuits) layout problem. We derive study properties strengthened semidefinite programming Max-Cut Our theoretical results hold every instance Max-Cut; particular, we make no assumptions about edge weights. The first provides strengthening well-known GoemansWilliamson relaxation, second further tightening first. prove tighter automatically enforces triangle inequalities, fact stronger than simple addition inequalities Goemans-Williamson relaxation. fully characterizes some low dimensional faces cut polytope via rank its feasible matrices. also address practical issues arising solution present showing remarkably bounds computed For problem, extending “tar-