Halldorsson's algorithm (WSP)

wsp.py

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[0]
        greedy.append(x[0])
        greedy_weight += x[1]
        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)])