All Questions
Tagged with max-cut ds.algorithms
10 questions
9
votes
1
answer
375
views
Positive cut algorithm on bipartite graphs with negative weights
Let $G=(V,E,w)$ be a bipartite graph with weight function $w:E→\{-1,1\}$. Is there an efficient (polynomial) algorithm for finding some positive (not necessarily maximum) cut of $G$, if one exists? If ...
- 91
3
votes
0
answers
226
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 ...
- 31
3
votes
1
answer
2k
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 ...
- 725
3
votes
0
answers
162
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 ...
- 573
12
votes
2
answers
528
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 ...
- 121
11
votes
1
answer
474
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 ...
- 537
9
votes
1
answer
4k
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 more involved approximation algorithms can be found here. The Max k-Cut problem is defined as follows.
Input is a graph G = ...
- 3,450
13
votes
4
answers
870
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 ...
- 9,910
8
votes
2
answers
1k
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 ...
- 1,478
39
votes
3
answers
5k
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 ...
- 9,910