4
$\begingroup$

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). 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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

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 get a factor 1/e, and improve this further in a subsequent paper with Buchbinder.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ A $1/2$ approximation is known. See a previous question on this topic.cstheory.stackexchange.com/questions/3593/… $\endgroup$
    – Chandra Chekuri
    Commented Aug 29, 2015 at 3:33
  • $\begingroup$ 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)$$. $\endgroup$
    – Tiratat Patana-anake
    Commented Aug 30, 2015 at 13:42
  • 1
    $\begingroup$ 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 arxiv.org/pdf/1409.5900.pdf $\endgroup$
    – Chandra Chekuri
    Commented Sep 2, 2015 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.