O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev · 2005
We give O(√log n)-approximation algorithms for the MIN UNCUT, MIN 2CNF DELETION, DIRECTED BALANCED SEPERATOR, and DIRECTED SPARSEST CUT problems. The previously best known algorithms give an O(log n)-approximation for MIN UNCUT [9], DIRECTED BALANCED SEPERATOR [17], DIRECTED SPARSEST CUT [17], and an O(log n log log n)-approximation for MIN 2CNF DELETION [14].We also show that the integrality gap of an SDP relaxation of the MINIMUM MULTICUT problem is Ω(log n).