max - Solving stochastic maximum bipartite matching problem -

-

i have faced following problem:

  • there 2 disjoint sets, a , b
  • for each pair of elements (a, b) (a belongs set a, b belongs set b) there probability pij known in advance. represents probability (certainty level) a matches b, or in other words, how closely a matches b (and vice-versa, because pij == pji).
  • i have find matching highest probability/certainty , find out pairs (a, b) describe matching
  • every element must matched / paired other set once (like in standard bipartite matching problem)
  • if possible, compute number approximately expresses uncertainty level obtained matching (let's 0 represents random guess , 1 represents certainty)

a simple practical example in such algorithm required described below (this not problem solving!):

  • two people asked write letters - z on piece of paper
  • for each pair of letters (a, b) run pattern matcher determine probability letter a written person a represents letter b wrote person b. gives probability matrix expresses kind of similarity correlation each pair of letters (a, b)
  • for each letter person a wrote, need find corresponding letter written person b

current approach: wondering if assign weights proportional logarithm of certainty level / probability element a set a matches element b set b , run maximum weighted bipartite matching find maximum sum. logarithm because want maximize total probability of multiple matching, , since single matches (represented pairs of matched elements a - b) form chain of events, product of probabilities, taking logarithm converts sum of probabilities, maximized using algorithm weighted bipartite matching, such hungarian algorithm. somehow doubt approach ensure best matching in terms of statistical expected maximum.

after searching bit, closest problem found two-stage stochastic maximum weighted matching problem, np-hard, need kind of "one-stage" stochastic maximum weighted matching problem.

i wonder if can use maxflow/mincut. can't prove it's optimal @ moment, problem may np-hard anyway. can use mf/mc find perfect matching when have bipartite graph v=(a,b) creating source connected nodes in weight of 1 , sink connected nodes in b weight 1. i'm proposing make weights of edges cross b probabilities mentioned above. think?


Comments

Post a Comment

Popular posts from this blog

c# - How to set Z index when using WPF DrawingContext? -

-
how set z-index drawing object when using drawingcontext.drawxxx() methods? the object drawn last have higher z index. can't change index of drawn objects. way draw in order. if using wpf (as placed tag), can use, example, canvas control. create shapes need like polyline obj = new polyline(); //... // ... set properties of obj and add them canvas uielementcollection: yourcanvasname.children.add(obj); //or yourcanvasname.children.insert(i, obj); first items of collection have higher z index. advantages in way: no need redraw on window changes, can anytime move objects , change order.
Read more

razor - Is this a bug in WebMatrix PageData? -

-
i think may have found bug in webmatrix's pagedata, not sure. concerns how pass data partial page calling page. in webmatrix documentation (tutorials, e.g. " 3 - creating consistent look ", , example code), pagedata recommended mechanism pass data between pages (e.g. content page layout page, or partial page). however have found not work other way, pass data partial page calling page. modifying or adding entries in pagedata in partial page, not seem calling page. cutting right down simplest possible example, in test page may have this: @{ pagedata["test"] = "initial entry"; } <p>before calling partial page, test value @pagedata["test"]</p> @renderpage("_testpartial.cshtml") <p>after returning calling page, test value @pagedata["test"]</p> and in _testpartial.cshtml page might have this: @{ pagedata["test"] = "modified entry"; } <p>in partial page...
Read more

visual c++ - Using relative values in array sorting ( asm ) -

-
i need sort through array , sort each individual row in array in ascending order. doesn't seem going (surprise!) keep getting hit 2 errors: a2101: cannot add 2 relocatable labels , a2026: constant expected here's sort, makes sense me, think i'm still trying implement high-lvl language techniqes assembly. there way around not being able use relative values? (the array 7 rows 9 columns, btw). mov cx, 7; cx = number of rows outer: ; outer loop walk through rows push cx mov cx, 9 mov row, cx ;rows middle: ; middle-loop walk through columns push cx sub cx, 1 ;cx = cx-1 mov column, cx ;columns inner: ;inner loop - compare , exchange column values cmp marray[row*9 + column], marray[row*9 + column+1] xchg marray[row*9 + column+1], marray[row*9 + column] ; compare , exchange values marray table inc column loop inner pop cx loop mid...
Read more