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 фрилансеров(-а) в среднем готовы выполнить эту работу за $54
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.