Seminar: The Maximum Weighted Independent Set with Applications in Wireless Networks and Protein Docking
Dreese Laboratories, room 260
Columbus, OH 43210
Sponsored by the Columbus Chapter of the IEEE Signal Processing Society
Prof. Yannis Paschalidis
Dept. of Electrical & Computer and of Systems Engineering
As one of the most challenging problems in graph theory, the problem of finding the Maximum Weighted Independent Set (MWIS) can be stated as follows: for a graph where each node is assigned a weight, select a set of nodes, no two of which are adjacent, with the largest possible total weight. In this talk I will discuss a new, novel, and fully distributed algorithm we have developed for the MWIS. The algorithm consists of two phases, each of which requires only local information and is based on message passing between the nodes of the graph. The first phase solves the linear programming relaxation of the MWIS problem, and in the second phase we construct a feasible solution to the MWIS problem using either a deterministic or a randomized estimation algorithm. We show that our algorithm always outputs an optimal solution to the MWIS problem for bipartite graphs with the deterministic estimation method, and provides a probabilistic performance guarantee for general graphs with heavy weights using the randomized estimation algorithm. I will illustrate the efficacy of the new algorithm in two very different applications domains: scheduling in wireless networks and protein docking.
Yannis Paschalidis is a Professor and Distinguished Faculty Fellow of Electrical & Computer and of Systems Engineering at Boston University, and a Co-Director of the Center for Information and Systems Engineering (CISE). He obtained a Diploma (1991) from the National Technical University of Athens, and an M.S. (1993) and a Ph.D. (1996) from the Massachusetts Institute of Technology (MIT), all in Electrical Engineering and Computer Science. In September 1996 he joined Boston University where he has been ever since. His current research interests lie in the fields of systems and control, networking, applied probability, optimization, operations research, computational biology, and bioinformatics. His recent work has found applications in communication and sensor networks, protein docking, logistics, cyber-security, robotics, the smart-grid, and finance.
Prof. Paschalidis' work on communication and sensor networks has been recognized with a CAREER award (2000) from the National Science Foundation, the second prize in the 1997 George E. Nicholson paper competition by INFORMS, and the best student paper award at the 9th Intl. Symposium of Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt 2011) won by one of his Ph.D. students for a joint paper. He was an invited participant at the 2002 Frontiers of Engineering Symposium, organized by the National Academy of Engineering.
His work on protein docking has been recognized by a first prize in the Protein Interaction Evaluation Meeting (2007) and a recognition (with his collaborators) for best performance in modeling selected protein-protein complexes against 64 other predictor groups that combine software models with human analysis (2009 Protein Interaction Evaluation Meeting). He has served in the program/organization committees of many conferences, has been a past associate Editor of the IEEE Transactions on Automatic Control and of the Operations Research Letters, and is currently an associate editor of the SIAM Journal on Control and Optimization, of the ACM Transactions on Sensor Networks, and of Operations Research.
Host: Ness Shroff