A combinatorial design approach to MAXCUT

✍ Scribed by Thomas Hofmeister; Hanno Lefmann

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 710 KB
• Volume: 9
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199608/09)9:1/2<163::aid-rsa10>3.0.co;2-p

✦ Synopsis

The k-MAXCUT problem for undirected graphs C = (V, E ) consists of finding a partition V = V , U . . . U V, such that the number of edges with endpoints in two different sets V, is maximized. We offer a new approach to this problem by showing that the combinatorial notion of block designs can be used to algorithmically obtain partitions for which until now only existence proofs were known. In the case of k = 2, we show that already known approaches can be improved by giving a simpler linear time algorithm which yields better bounds. In particular, we give a linear time algorithm which achieves a bound of Edwards [12]. For general k = 2' and graphs with rn edges, we are able to compute efficiently partitions of size rn . (kl ) / k . (1 + 1 /(A + kl ) ) , where A is the maximum degree of G.

The algorithms can also be applied to weighted graphs.