The max-cut tag has no wiki summary.
2
votes
1answer
49 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
106 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
272 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
352 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
128 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 ...
1
vote
1answer
393 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
118 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
363 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
272 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
593 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 ...
8
votes
1answer
488 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
154 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 ...
7
votes
1answer
424 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
417 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
327 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 ...
28
votes
3answers
1k 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 ...
