Approximatiom and Polynomial-time Algorithms for Structured Optimization

点击翻译按钮获取中文摘要

This research addresses theoretical and computational aspects of structured optimization: polynomial-time algorithms, fully polynomial-time approximation schemes, complexity issues related to semidefinite programming, and numerical experimentation. The goals are: (1) to study the efficiency of widely-used Lagrangian decomposition techniques with emphasis on the development of nearly-optimal potential-reduction methods; (2) to study general block-angular and linear bordered block-diagonal problems, and, time permitting, their specialized applications in combinatorics, operations research, communications, engineering and finance; (3) to explore the complexity of semidefinite programming with real and integer variables; and (4) to conduct computational experiments which will examine the numerical behavior and practical performance of the developed algorithms.