<p>This is a special case of non-monotone submodular maximization with a cardinality constraint, and constant factor approximation algorithms are known. For example, <a href="http://theory.epfl.ch/moranfe/Publications/FOCS2011.pdf" rel="nofollow">Feldman, Naor, and Schwartz</a> get a factor 1/e, and improve this further in a <a href="http://theory.epfl.ch/moranfe/Publications/SODA2014.pdf" rel="nofollow">subsequent paper with Buchbinder</a>.</p>

CC BY-SA 3.0
2015-08-29T03:33:22.877Z
A $1/2$ approximation is known. See a previous question on this topic.http://cstheory.stackexchange.com/questions/3593/approximation-algorithms-for-max-cut-when-sizes-of-partition-sets-are-fixed
Chandra Chekuri
CC BY-SA 3.0
2015-08-30T13:42:02.170Z
I ended up implementing Discrete Random Greedy because it gives a good approximation factor, pretty easy to implement than others and also because it's not too slow.

I was considering the Local search algorithm but it would be too slow since it has $$O(n^k)$$.
Tiratat Patana-anake
CC BY-SA 3.0
2015-09-02T18:40:00.353Z
Max-Cut is a symmetric submodular function. For symmetric non-negative functions there is a better than 1/e approximation due to a recent result of Moran Feldman. See http://arxiv.org/pdf/1409.5900.pdf
Chandra Chekuri
CC BY-SA 3.0
2015-08-28T23:21:12.123Z
2015-08-28T23:21:12.123Z
Sasho Nikolov
<p>Here's my problem,</p>

<blockquote>
  <p><strong>Problem:</strong> Given a weighted undirected graph $G=(V,E,w)$ with weight function $w:E\rightarrow\mathbb{R}$ and an integer $k$, find a cut $S$ of graph $G$ such that $|S| \leq k$ and maximize the total weight of edges crossing the cut $S$.</p>
</blockquote>

<p>This is a real world problem in Genetics. With the number of vertices, $|V|$, about 1,600, and $k$ about 15.</p>

<p>Each vertices in $G$ is a person, and edges are how much two people are <em>related</em> (<a href="https://en.wikipedia.org/wiki/Coefficient_of_relationship" rel="nofollow">kinship coefficient</a>). We want to pick people to do a full genome (DNA) sequence so that we maximize the amount of DNA shared between the selected people and the rest of the pedigree, but we also don't want to spend money to sequence every people.</p>

<p>Approximation algorithm is okay.</p>

<p>Do you know any algorithm or paper that might help me with this problem?</p>

CC BY-SA 3.0
2015-08-30T00:56:46.360Z
possible duplicate of [Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed](http://cstheory.stackexchange.com/questions/3593/approximation-algorithms-for-max-cut-when-sizes-of-partition-sets-are-fixed)
Sasho Nikolov
<reference-request><graph-algorithms>
Maximum size-k cut
Tiratat Patana-anake
# Maximum size-k cut

(Asked by: username_0 on 2015-08-28)

Here's my problem,

> **Problem:** Given a weighted undirected graph $G=(V,E,w)$ with weight function $w:E\rightarrow\mathbb{R}$ and an integer $k$, find a cut $S$ of graph $G$ such that $|S| \leq k$ and maximize the total weight of edges crossing the cut $S$.

This is a real world problem in Genetics. With the number of vertices, $|V|$, about 1,600, and $k$ about 15.

Each vertices in $G$ is a person, and edges are how much two people are *related* ([kinship coefficient](https://en.wikipedia.org/wiki/Coefficient_of_relationship)). We want to pick people to do a full genome (DNA) sequence so that we maximize the amount of DNA shared between the selected people and the rest of the pedigree, but we also don't want to spend money to sequence every people.

Approximation algorithm is okay.

Do you know any algorithm or paper that might help me with this problem?

**Tags:** reference-request, graph-algorithms
> **Comments:**
> **username_1**: possible duplicate of [Approximation algorithms for MAX-CUT, when sizes of partition sets are fixed](http://cstheory.stackexchange.com/questions/3593/approximation-algorithms-for-max-cut-when-sizes-of-partition-sets-are-fixed)  

---

## 1 answers

### Answer by username_1 on 2015-08-28. Score: 2 | Accepted answer

This is a special case of non-monotone submodular maximization with a cardinality constraint, and constant factor approximation algorithms are known. For example, [Feldman, Naor, and Schwartz](http://theory.epfl.ch/moranfe/Publications/FOCS2011.pdf) get a factor 1/e, and improve this further in a [subsequent paper with Buchbinder](http://theory.epfl.ch/moranfe/Publications/SODA2014.pdf).

> **Comments:**
> **username_2**: A $1/2$ approximation is known. See a previous question on this topic.http://cstheory.stackexchange.com/questions/3593/approximation-algorithms-for-max-cut-when-sizes-of-partition-sets-are-fixed  
> **username_0**: I ended up implementing Discrete Random Greedy because it gives a good approximation factor, pretty easy to implement than others and also because it's not too slow.  I was considering the Local search algorithm but it would be too slow since it has $$O(n^k)$$.  
> **username_2**: Max-Cut is a symmetric submodular function. For symmetric non-negative functions there is a better than 1/e approximation due to a recent result of Moran Feldman. See http://arxiv.org/pdf/1409.5900.pdf  

---

