Dr. Gordon Wilfong

“Approximation Algorithms for Constrained Knapsack Problems”

Thursday, November 12, 4:00 PM

Packard Lab room 466

Reception prior to talk in Packard Lobby

Abstract: We study various versions of the constrained knapsack problem. One everyday example of such a problem is where you are organizing a party but you don't have the space to invite everyone you know. Also each of your friends will come only if at least one (or, seemingly, worse -- all) of their friends also come. So who do you invite so that as many people as possible come without exceeding the capacity of your room?

Such a social network can be modeled as a graph with nodes representing people and edges representing friendships. The graph might be undirected or directed (e.g., I might come to the party if you do, but you might not care if I'm there.) Some friend might be more valuable to have at a party and some may take up more space than others. These can be modeled as well.

We give hardness results and approximation algorithms for such constrained knapsack problems where the graph of constraints is either directed or undirected and the nodes can have uniform or arbitrary
weights and/or profits. (This is joint work with Glencora Borradaile (Oregon State U) and Brent Herringa (Williams College)

Bio: Gordon Wilfong is a Distinguished Member of Technical Staff in the Computing and Software Principles Research Department at Bell Labs in Alcatel-Lucent. His major research interests are in the design and analysis of algorithms.

Dr. Wilfong received his B.Sc., First Class Honours, in mathematics from Carleton University in 1980 and his M.S. and Ph.D. in computer science from Cornell University in 1983 and 1984 respectively."