Computer Science Colloquium

Approximation algorithms produce approximate solutions, along with a performance guarantee, to instances of NP-hard problems, providing a means of attack at problems which are widely believed to be intractable. Polyhedral analysis is an area of classical mathematics which has also enjoyed a growing and diverse audience due to the seemingly ubiquitous applicability of linear programming both as a practical and theoretical tool. My talk will focus on polyhedral approaches to the weighted edge dominating set problem in graphs, a fundamental network design problem in which we seek to cover all the edges of a graph with a minimum weight set of edges. I will present the first approximation algorithms for this problem, culminating with a 2-approximation algorithm, and show that the problem is in fact equivalent to a generalization of the famous weighted vertex cover problem, that of covering the edges of a graph with a minimum weight set of vertices. I will also present approximation algorithms for variants of the problem in which we seek an edge dominating set that must be connected or a tour.

Ojas Parekh is a student in the Algorithms, Combinatorics, and Optimization program at Carnegie Mellon Univeristy, expecting to complete his Ph.D. this summer. Ojas received his undergraduate degree at Georgia Tech, and considers The South(east) his home.