Need help solving optimization problems? The IE Decisions System Engineering Fall ’16 Seminar Series event hosted by Giulia Pedrielli can help optimize bounds for a variety of task scheduling issues.
Greedy Strategies and Submodular Optimization
Presented by Edwin K. P. Chong, professor, Department of Electrical and Computer Engineering and Department of Mathematics at Colorado State University
Friday, October 21, 2016
noon
Brickyard Engineering (BYENG) 210, Tempe campus [map]
Abstract
We discuss optimization problems where the objective function is submodular, which roughly means that it has the property of diminishing returns. In such problems, we can provably bound the performance of the greedy solution relative to the optimal solution. We present a variety of recent results related to such optimization problems, including bounds for “stringsubmodular” problems, bounds related to k-batch greedy strategies, improved bounds involving notions of curvature, and bounds on Nash equilibria in submodular games. We illustrate these results in the context of various application problems arising in task scheduling.
Bio
Edwin K. P. Chong received the bachelor’s degree with First Class Honors from the University of Adelaide, South Australia, in 1987; and his mater’s and doctoral degrees in 1989 and 1991, respectively, both from Princeton University, where he held an IBM Fellowship. He joined the School of Electrical and Computer Engineering at Purdue University in 1991, where he was named a University Faculty Scholar in 1999. Since August 2001, he has been a Professor of Electrical and Computer Engineering and Professor of Mathematics at Colorado State University. He coauthored the best-selling book, An Introduction to Optimization (4th Edition, Wiley-Interscience, 2013). He received the NSF CAREER Award in 1995 and the ASEE Frederick Emmons Terman Award in 1998. He was a corecipient of the 2004 Best Paper Award for a paper in the journal Computer Networks. In 2010, he received the IEEE Control Systems Society Distinguished Member Award. Prof. Chong is a Fellow of IEEE. He was the founding chairman of the IEEE Control Systems Society Technical Committee on Discrete Event Systems, and served as an IEEE Control Systems Society Distinguished Lecturer. He is currently a Senior Editor of the IEEE Transactions on Automatic Control, and has also served on the editorial boards of Computer Networks, Journal of Control Science and Engineering, and IEEE Expert Now. He was the General Chair for the 2011 Joint 50th IEEE Conference on Decision and Control and European Control Conference. He has served as a member of the IEEE Control Systems Society Board of Governors and as Vice President for Financial Activities until 2014. He currently serves as President-Elect.
