Approximation algorithms for packing and network problems

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

A large number of practical optimization problems belong to the class NP-hard and, unfortunately, there is strong theoretical evidence suggesting that optimum solutions for NP-hard problems cannot be computed efficiently. Approximation algorithms are fundamental tools for dealing with this class of problems, as these algorithms can efficiently produce solutions that are guaranteed to be at most some factor c away from the optimum. Thus, a natural goal when designing approximation algorithms is to make this factor c as close to 1 as possible. In this research we are mainly interested in studying approximation algorithms for NP-hard optimization problems of two classes: packing and network problems. Networks are one of the most fundamental modeling tools in optimization, with applications to a large number of fields. Packing problems are of great importance in transportation, VLSI design, scheduling, and any other area requiring the arrangement of objects in bounded spaces.