4 2, 3, 4 4 2, 3, 4, 8 2, 4, 5, 8 3, 4, 6, 8 5 3, 5, 7, 11, 17 6 4, 5, 10, 13, 16, 30 7 5, 17, 21, 25, 31, 37, 55 8 5, 17, 21, 25, 31, 37, 55, 93 7, 11, 19, 25, 31, 41, 51, 93 9 15, 25, 39, 53, 65, 69 [...] analysis instead of Wmax. Consider for example the weights W = (3, 7, 11, 19, 31) and ` = 3. These weights can be replaced by w = (1, 2, 4, 7, 12), because fW (x)−fW (x′) = Pn i=1 Wixi− Pn i=1 Wix ′ i has [...] Wmax)) RLS 2 |E| O(|E|2 log |E|) Basis [7] (1+1) EA |E| |E||E|/2 O(|E|3 log |E|) Weighted Matroid O(|E|4(log r(E) + log Wmax)) RLS3 3 2|E| O(|E|5) Intersection [7] (1+1) EA |E| |E||E|/2 O(|E|5 log |E|) …