Graduate Exam Abstract
Yajing Liu
Ph.D. Preliminary
October 24, 2017, 2:00 pm - 4:00 pm
C101B ECE Conference Room
Performance Bounds for the Greedy Strategy in Optimization Problems
Abstract: The greedy strategy is an
approximation algorithm to solve
optimization problems where the
optimal solution is hard to obtain. We
consider two classes of optimization
problems. The first is set optimization,
which is to choose a set of actions to
optimize an objective function, and the
second is string optimization, which is
to choose an ordered set of actions to
optimize an objective function. This
presentation aims to: 1) provide
performance bounds for the greedy
strategy in string optimization
problems under matroid constraints; 2)
provide performance bounds for the
batched greedy strategy in set
optimization problems under matroid
constraints; 3) provide performance
bounds for group Nash equilibria in
game theory.
Adviser: Edwin K.P. Chong
Co-Adviser: Ali Pezeshki
Non-ECE Member: Dan Bates, Mathematics
Member 3: J. Rockey Luo, ECE
Addional Members: N/A
Publications:
1: Y. Liu, E. K. P. Chong, A. Pezeshki, and W. Moran, "Bounds for approximate dynamic programming based on string optimization and curvature," in Proceedings of the 53rd IEEE Conference on Decision and Control, Los Angeles, CA, December 15--17, 2014, pp. 6653--6658.
2: Y. Liu, E. K. P. Chong, and A. Pezeshki, "Bounding the greedy strategy in finite-horizon string optimization," in Proceedings of the 54th IEEE Conference on Decision and Control, Osaka, Japan, December 15--18, 2015, pp. 3900--3905.
3: Y. Liu, E. K. P. Chong, and A. Pezeshki, "Performance bounds for the k-batch greedy strategy in optimization problems with curvature," in Proceedings of the 2016 American Control Conference, Boston, Massachusetts, July 6--8, 2016, pp. 7177--7182.
4: Y. Liu, Z. Zhang, E. K. P. Chong, and A. Pezeshki, "Performance bounds with curvature for batched greedy optimization," Journal of Optimization Theory and Applications, to appear.
5: Y. Liu, E. K. P. Chong, and A. Pezeshki, "Performance bounds for Nash equilibria in submodular utility systems with user groups," Journal of Control and Decision, to appear.
6: Y. Liu, E. K. P. Chong, and A. Pezeshki, "Improved Bounds for the Greedy Strategy in Optimization Problems with Curvatures," Discrete Applied Mathematics, under review.
Program of Study:
ECE512
ECE513
ECE514
ECE516
ECE651
ECE652
ECE656
STAT720
