QTDDTOB

Revision ru1, by Xellos, 2017-05-24 18:53:52

Questions That Don't Deserve Their Own Blog — I guess it'd be good to have something like this as a place to ask random questions about problems ("I accidentally my code, wat do?") without having your blog post get downvotebombed?

I have a question about Yandex.Algorithm 2015 round 2.2E: the problem can be reduced to computing the min. bipartite vertex cover that can't fully cover one side and since the dual of min. vertex cover is max. matching, I tried to find the dual of this problem.

I mean, that vertex cover can be described as a linear programming problem

  • xi ≥ 0
  • xuj + xvj ≥ 1 for each edge ej = (uj - vj), 1 ≤ j ≤ E

Its dual should be

  • for 1 ≤ i ≤ N, (sum over edges incident on vertex i in the left part)
  • for N + 1 ≤ i ≤ N + M, (same as above for the right part)

yj are variables assigned to edges (flow through them); are assigned to the left and right part of the graph and if they're fixed, finding the optimal yj is just bipartite matching/flow. However, this gives the optimal solution as for example for an almost complete bipartite graph KN, N that's missing just one edge, which doesn't make sense.

What am I missing here?

Tags random, programming, questions

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Xellos 2017-06-10 02:26:23 0 Tiny change: 'Questions ' -> ' Questions '
ru2 Russian Xellos 2017-06-09 18:58:33 6144
en2 English Xellos 2017-06-09 15:38:22 6144
en1 English Xellos 2017-05-25 11:47:52 1766 Initial revision for English translation
ru1 Russian Xellos 2017-05-24 18:53:52 1766 Первая редакция (опубликовано)