## Posts Tagged ‘HermanshuKaul’

### Hermanshu Kaul, Finding Large induced subgraphs and allocation of resources under dependeny

Tuesday, October 29th, 2013
Finding Large induced subgraphs and allocation of resources under dependeny
Hermanshu Kaul
Illinois Institute of Technology
2013/11/20 Wednesday 4PM-5PM
Room 1409

Given a graph, we are interested in studying the problem of finding an induced subgraph of a fixed order with largest number of edges. More generally, let G = (V, E) be an undirected graph, with a weight (budget) function on the vertices, w: V → ℤ+, and a benefit function on vertices and edges b: EV → ℤ. The benefit of a subgraph H =(VH,EH) is b(H) = ∑ v∈VH b(v) + ∑ e∈EH b(e) while its weight is w(H) = ∑ v∈VH w(v). What can be said about the maximum benefit of an induced subgraph with the restriction that its weight is less than W?

This problem is closely related to the Quadratic Knapsack Problem, the Densest Subgraph Problem, and classical problems in Extremal Graph Theory. We will discuss these connections, give applications in resource allocation, and present new results on approximation algorithms using methods from convex optimization and probability. This is joint work with Kapoor.