For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max-cut problem.

learn more… | top users | synonyms

20
votes
2answers
596 views

Max-Cut algorithm that shouldn't work, unclear why

OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic: Given an undirected graph $G=(V,E)$, ...
-2
votes
2answers
109 views

MAX Cut with an oracle

Suppose that I have a MAX CUT problem on a weighted undirected Graph $G$, but there is an oracle that tells me what the value of the MAX CUT is, but not which edges produce it. Does this make the ...
5
votes
1answer
135 views

Best approximation for a HYPERGRAPH-MAXDICUT problem

Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every ...
3
votes
2answers
175 views

Size of MAXCUT from eigenvalues

Is there an interpretation of MAXCUT using eigenvalues of the graph that yields constant factor approximation to MAXCUT? Can the estimates provide sharp lower bound to MAXCUT?
2
votes
1answer
60 views

partition to min the max number of intersections

Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any ...
3
votes
1answer
166 views

What is this matrix column-selection problem, and how hard is it to approximate?

I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place ...
7
votes
3answers
313 views

Hardness of MAX-CUT on sparse graphs

Let a weighted graph $G(V,E)$, where the weights are real (positve and negative). Assume that $G$ has $\mathcal{O}(n\log n)$ edges. How fast can we compute MAX-CUT on this graph? Can we compute ...
8
votes
1answer
389 views

Is Max-Cut APX-complete on triangle-free graphs?

In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph such that the number of edges between S and the complement of S is as large as possible. Max-Cut is ...
3
votes
0answers
144 views

The Quality of SDP relaxation on MaxCut

My question is: given a maxcut instance, if it costs too much to solve it to optimal practically but we can get an optimal solution of SDP relaxation quickly, can we assess the quality of this SDP ...
2
votes
1answer
515 views

Max-cut via linear programming or sdp

I am looking for a linear programming formulation for the max-cut problem. My interest is to know about the primal - dual algorithm for max-cut. It would be nice if someone can tell me that what is ...
2
votes
0answers
123 views

Gram matrix of Max-Cut relaxation

It seems that Goemans and Williamson give a unique representation for each graph of the semidefinite relaxation (elements $y_{ij}$ of Y). However, semidefinite programming may give the same maximum ...
11
votes
2answers
389 views

Euclidean-squared max-cut in low dimensions

Let $x_1, \ldots, x_n$ be points in the plane $\mathbb{R}^2$. Consider a complete graph with the points as vertices and with edge weights of $\|x_i - x_j\|^2$. Can you always find a cut of weight that ...
9
votes
1answer
302 views

Examples of hard instances for Goemans and Williamson algorithm

I'm interested in the explicit examples of graphs for which application of Goemans and Williamson algorithm for approximating maximum cuts results in 0.878…-approximation factor. The algorithm to ...
7
votes
1answer
832 views

What's the approximation factor of this Max k-Cut approximation?

I'm thinking about an approximation algorithm for Max k-Cut. One simple and another one advance approximation algorithms are available here. The Max k-Cut problem is defined as follow: Assume we ...
10
votes
1answer
558 views

$\epsilon$-nets with respect to the cut norm

The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in ...
3
votes
0answers
161 views

Complexity of Max Bisection on cubic planar graphs?

Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximum. Max Bisection is $NP$-complete on cubic graphs and also on planar ...
8
votes
1answer
478 views

Is MAX CUT approximation resistant?

CSP optimization problem is approximation resistant if it is $NP$-hard to beat the approximation factor of a random assignment. For instance, MAX 3-LIN is approximation resistant since a random ...
12
votes
3answers
469 views

A Multi-cut Problem

I'm looking for a name or any references to this problem. Given a weighted graph $G = (V, E, w)$ find a partition of the vertices into up to $n = |V|$ sets $S_1,\ldots,S_n$ so as to maximize the ...
3
votes
2answers
369 views

Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed

The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the ...
29
votes
3answers
2k views

Max-cut with negative weight edges

Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find: $$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$ If the ...