2d
comment Maximum size-k cut
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
Sep
1
awarded Nice Answer
Aug
29
comment Maximum size-k cut
A $1/2$ approximation is known. See a previous question on this topic.cstheory.stackexchange.com/questions/3593/…
Aug
17
awarded Yearling
Aug
17
awarded Yearling
Aug
14
awarded Good Answer
Aug
12
answered Survivable networks, directed case
Jul
4
answered What are some of the most ingenious linear programs developed for tackling hard combinatorial problems?
Jun
26
comment How expensive may it be to destroy all long s-t paths in a DAG?
Sorry, I misunderstood the question. Thanks for the other reference.
Jun
25
comment How expensive may it be to destroy all long s-t paths in a DAG?
Length bounded flows and cuts are closely related to the questions you ask. I recommend looking at the thesis of Baier. ftp.math.tu-berlin.de/pub/Preprints/combi/…
Jun
18
comment Reservoir sampling of distinct values
Papers on $\ell_0$ sampling, namely sampling distinct elements are what you may be looking for. Here is one paper: arxiv.org/abs/1012.4889
Jun
9
comment Structure of graphs that exclude a perfect matching on four vertices as an induced graph
Want to add here an important property of the $2K_2$-free graphs, namely that the number of maximal independent sets in such graphs is polynomial in the number of vertices. In fact for any fixed $t$ $tK_2$-free graphs have a polynomial number of maximal independent sets. See following ref for more information. "Complexity results on graphs with few cliques." Discrete Mathematics and Theoretical Computer Science 9.1 (2007): 127-135.
Jun
8
awarded Enlightened
Jun
7
awarded Nice Question
Jun
5
awarded Scholar
Jun
5
comment Structure of graphs that exclude a perfect matching on four vertices as an induced graph
Thanks David. I predicted that you would answer it :).
Jun
5
accepted Structure of graphs that exclude a perfect matching on four vertices as an induced graph
Jun
5
awarded Student
Jun
5
asked Structure of graphs that exclude a perfect matching on four vertices as an induced graph
May
20
answered Multidimensional knapsack STRONGLY NP-complete
1 2 3 4 5