Algorithmic Techniques for Optimization in Graphs

图优化的算法技术

• 批准号: 9700146
• 负责人: Philip Klein
• 金额: $ 22.92万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-08-01 至 2003-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9700146&HistoricalAwards=false
• 关键词: Algorithmic; Techniques; Optimization; Graphs

This project investigates algorithmic techniques for optimization, with an emphasis on problems related to graphs. The goal is faster and more space-efficient algorithms. A special focus is the use of semidefinite programming for modelling graph optimization problems. A new approach to approximately solving semidefinite programming problems is being pursued. Using the work on semidefinite programming as a guide, the project studies improving the efficiency of a broad class of approximation algorithms for optimization.

这个项目研究优化的算法技术，重点是与图相关的问题。我们的目标是更快、更节省空间的算法。一个特别的焦点是使用半定规划建模图优化问题。目前正在研究一种近似求解半定规划问题的新方法。以半定规划的工作为指导，本项目研究了提高一类优化近似算法的效率。