Algorithms for graph-constrained knapsack problems

November 3, 2009
Suppose you are planning a party, but you can only invite 20 people, (caviar is expensive).  You can’t invite more than 20 people, but you want to maximize the number (or perhaps worth) of people that will show up.  But an attendee will only come to your party if one of their friends is also attending.  How do you find a set of friends to invite?
More specifically, we are given a knapsack of capacity K and a graph representing constraints (i.e. friendships) between the nodes; each node has a weight and a profit.  The goal is to find a maximum-profit set of nodes of total weight at most K such that if node x is selected, then a neighbour of x is also selected.
It turns out that this knapsack problem models several interesting problems (albeit less important than party planning) such as: network formation, tool magazine management, database storage and strategical investing.  In this talk I will take you on a tour of greedy algorithms, approximation guarantees and hardness of approximation in solving the graph-constrained knapsack problem.

Versions of this talk have been given at the

  • School of EECS Colloquium, Oregon State University (November 2, 2009) to an audience dominated by first year EE and CS graduate students.
  • Combinatorial Potlatch, Vancouver, BC (November 21, 2009) to a raucous group of discrete mathematicians.

Joint work with Brent Heeringa (Williams College) and Gordon Wilfong (Bell Labs)

Suppose you are planning a party, but you can only invite 20 people, (caviar is expensive).  You can’t invite more than 20 people, but you want to maximize the number (or perhaps worth) of people that will show up.  But an attendee will only come to your party if one of their friends is also attending.  How do you find a set of friends to invite?

More specifically, we are given a knapsack of capacity K and a graph representing constraints (i.e. friendships) between the nodes; each node has a weight and a profit.  The goal is to find a maximum-profit set of nodes of total weight at most K such that if node x is selected, then a neighbour of x is also selected.

It turns out that this knapsack problem models several interesting problems (albeit less important than party planning) such as: network formation, tool magazine management, database storage and strategical investing.  In this talk I will take you on a tour of greedy algorithms, approximation guarantees and hardness of approximation in solving the graph-constrained knapsack problem.

[ keynote ] [ powerpoint - may contain errors due to conversion from keynote ]

Filed under: Talks by Glencora

Leave a Reply