Given a complete probabilistic network G =(V,E,l) (i.e. with each edges e weighted by a likelihood l(e) being a transmission link, e.g. l(e) ~ 1/d(e)), an α-spanning subnetwork (where α by default 95%) is a subnetwork N of G such that for any cut V= X+X’
(partitioning V into subset X and its complement X’=V-X), the sum of likelihoods of N-edges cut is at least α% of the total likelihood of G-edges cut. We want to find minimum α-spanning subnetwork, which is the one with the minimum number of edges.
Problem of finding α-spanning subnetwork.
We can solve this problem either by ILP or by the following greedy heuristic:
N <- empty
α-SPAN: Sort all edges in ascending order of likelihoods l(e)
Delete edges until vertices are partitioned into two disjoint vertex subsets X and V-X
Sort all edges between X and V-X by likelihood in descending order and add them to N until α% of the total likelihood is reached
Recursively apply α-SPAN for X and V-X
hi there, the first algorithm is a version of min cut- max flow problem and the second one relies on transitivity of \alpha-span. Contact me for more details.
Hello, I have just read your requirement very careful and I am sure that I can finish it for 1 hours because I am a professional C/C++ expert with strong algorithm.
Now I don't have even one review because I am a new freelancer.
So I think it is a important opportunity for me to prove my skill.
Please contact me if you want to finish it instantly.
Thank you for having a look.