# Questions tagged [max-cut]

Questions on the maximum cut problem, where one is given a graph and wants to find a subset of the vertex set such that number of edges between it and the complementary subset is as large as possible.

24 questions
Filter by
Sorted by
Tagged with
524 views

### Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E)$, and as long as you ...
2k views

### Reduction from PARTITION to MAX-CUT

I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT ...
1k views

### Maximum number of matched vertexes in a one-to-many bipartite graph

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...