Title: Graph-theoretic conflict resolution with applications in wireless networks and protein docking
Abstract: We consider graphs with nodes representing decisions and edges representing conflicts among two decisions. Nodes are further assigned weights indicating the reward of the corresponding decision. In such a graph, the Maximum Weighted Independent Set (MWIS) problem is to select a set of nodes, no two of which are adjacent, with the largest possible total weight. This is equivalent to selecting a "conflict-free" set of decisions with maximal reward. MWIS is NP-hard. I will present a new fully distributed algorithm consisting oftwo phases, each of which requires only local information and is based on message passing between nodes of the graph. The first phase solves a relaxation of MWIS, and the second phase constructs a feasible solution using a deterministic estimation algorithm. We show that our algorithm always outputs an optimal solution to MWIS for perfect graphs. I will illustrate the efficacy of the new algorithm in two very differentapplications domains: scheduling in wireless networks and protein docking.
About the speaker: Yannis Paschalidis is a Professor and Distinguished Faculty Fellow of Electrical and 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 systems and control, networking, applied probability, optimization, operations research, computational biology, medical informatics, and bioinformatics. His recent work has found applications in communication and sensor networks, protein docking, metabolic networks, logistics, cyber-security, robotics, the smart-grid, health care, 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. His work on protein docking has been recognized by a 1st 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 (2009 Protein Interaction Evaluation Meeting). He was an invited participant at the 2002 Frontiers of Engineering Symposium organized by the National Academy of Engineering. He has served in the program and organizing committees of numerous conferences and has been on the editorial board of several journals. He currently is the Editor-in-Chief of the IEEE Trans. on Network Systems.