Monday November 2 4:00 - 4:50 PM Kelley 1001 [map] <http://oregonstate.edu/cw_tools/campusmap/?&offsetX=1576&offsetY=526&po int=?298,111>
Glencora Borradaile Assistant Professor School of Electrical Engineering and Computer Science Oregon State University How to plan a party: algorithms for graph-constrained knapsack problems 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. Biography Glencora Borradaile is an Assistant Professor in the School of Electrical Engineering and Computer Science at Oregon State University. She has a Ph.D. in Computer Science from Brown University (2008), after which she did postdoctoral research at the University of Waterloo. She enjoys designing algorithms that work in some provable way (quickly, accurately) and is motivated by problems in routing, network design, and graph optimization.
_______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
_______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
_______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
