# please explain this algorithm

Budget $10-30 USD

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

## 5 freelancers are bidding on average $54 for this job

Hi, I have gone through your requirements and I can do this task. The skills and resources needed for this project are in my genes. I can assure you for a complete professional work in given time [login to view URL] share comp More

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 f More

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.

I'm an algorithms enthusiast and a competetive programmer. I can solve this problem and give you the detailed documentation. Using C++.