Skip to content

Instantly share code, notes, and snippets.

@joesavage

joesavage/wsp.py

Created Mar 17, 2019
Embed
What would you like to do?
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[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)])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment