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 of two 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 different applications domains: scheduling in wireless networks and protein docking.
 

演讲人简历　Yannis Paschalidis is a Professor and Distinguished Faculty Fellow of Electrical and Computer Engineering, Systems Engineering, and Biomedical Engineering at Boston University. He is the 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. He has been at Boston University since 1996. His current research interests lie in the fields systems and control, networking, applied probability, optimization, operations research, computational biology, medical informatics, and bioinformatics.

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 (with his collaborators) has been recognized 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 US National Academy of Engineering. Prof. Paschalidis is a Fellow of the IEEE and the Editor-in-Chief of the IEEE Transactions on Control of Network Systems.

 

联系人：赵千川 62783612, zhaoqc@tsinghua.edu.cn