The assignment problem consists of mapping jobs to machines for the minimization of some cost. The random assignment problem minimizes the cost in a setting where the job-on-machine costs are independent and identically distributed. A variation, one that arises in a computational linguistics problem of semantic projection, is to find the minimum cost edge-cover. In this talk, I will highlight the main steps in applying a technique known as the objective method to the minimum cost edge-cover problem. I will also discuss a belief propagation algorithm that converges to the optimal solution as the network size grows. The belief propagation algorithm is useful because, in addition to being amenable to parallel implementation, it yields a near optimal solution with lesser complexity in the above random context than the best known algorithms designed for worst-case optimality. (Based on joint work with Mustafa Khandwawala)
Rajesh Sundaresan got his BTech in Electrical Engineering from IIT Madras and PhD from Princeton University. He worked with Qualcomm for several years before joining the Department of Electrical Communication Engineering at the Indian Institute of Science, Bangalore, where he is an Associate Professor. He was a visiting scholar at the Coordinated Sciences Laboratory of the University of Illinois at Urbana-Champaign under an Indo-US Science & Technology Forum Fellowship. His research interests are in the areas of communication networks and information theory.