Continuous Approaches to Optimization Problems in Graphs

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

Discrete optimization problems arise in many important application areas, including computational biochemistry, social networks, telecommunications, and network-based analysis of big data. This award funds fundamental research to develop computationally efficient algorithms for solving hard discrete optimization problems using techniques from continuous optimization. In addition to fundamental contributions to discrete optimization, the results from this research may stimulate new developments in continuous optimization. The developed methodology will be integrated into the teaching curricula, as well as into research and educational programs at the undergraduate and graduate levels.While convex relaxations based on linear, semidefinite, and conic programming represent a common feature of exact algorithms for discrete optimization problems, their non-convex counterparts have not been studied in this context, even though some of them can be solved efficiently. This research is to fill this gap by investigating non-convex relaxations of optimization problems that admit binary quadratic formulations (e.g., the maximum clique/independent set problems, minimum vertex cover, max-cut, etc.). This research will develop and analyze new continuous non-convex formulations of discrete problems; derive new optimality conditions for discrete optimization problems based on their continuous nonlinear formulations; deduct important computational complexity results for general and special cases of continuous optimization; obtain lower and upper bounds based on nonlinear formulations that can be utilized in designing exact branch-and-bound algorithms; and design approximation algorithms (with provable approximation ratio) based on non-convex, polynomial-time solvable relaxations.