Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# joesavage/wsp.py

Created Mar 17, 2019
Halldorsson's algorithm (WSP)
 from math import sqrt # Find an approximate solution to the weighted set packing problem using # Halldorsson's algorithm (2000). Our approximate solution is at worst only a # factor of sqrt(m) worse than the optimal solution. # # Input: # S = { a, b, c... } # Set of base elements (m = |S|) # C = { C_1, C_2, C_3, ... } # Collection of weighted subsets of S # C_i = ({ a, c, ... }, weight) # Weighted subset of S # # Output: # C' = { C_1, C_3, ... } # Subcollection of disjoint sets from C with # # approximately maximum weight def WSP(m, collection): fallback, fallback_weight = max(collection, key=lambda (s, w): w) # Greedily select sets of maximum weight that are disjoint from the # previously selected sets, taking from a collection only containing sets # of cardinality less than or equal to sqrt(m). used = set() greedy = list() greedy_weight = 0 collection = [(s, w) for s, w in collection if len(s) <= sqrt(m)] while collection: x = max(collection, key=lambda (s, w): w / sqrt(len(s))) used |= x greedy.append(x) greedy_weight += x collection = [(s, w) for s, w in collection if not s & used] # Select between the greedy solution or the fallback solution return greedy if greedy_weight > fallback_weight else [fallback] print WSP(10, [({ 'A', 'B' }, 0.29), ({ 'A', 'C' }, 0.29), ({ 'B', 'C' }, 0.29), ({ 'A', 'B', 'C' }, 0.57), ({ 'B', 'E' }, 0.14), ({ 'D', 'E' }, 0.19), ({ 'A', 'E' }, 0.1), ({ 'A' }, 0.05)])
to join this conversation on GitHub. Already have an account? Sign in to comment