Computational Models and Efficient Algorithm Design for Discrete Optimization Problems

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

Many interesting discrete optimization problems are computationally intractable (NP-Hard), i.e., there are no algorithms to find optimal solutions to such problems in polynomial time. In some situations, the complete input is not known in advance, for example, the input is a request sequence that is revealed gradually over time. Under the lack of information on future requests, the algorithm has to perform well. In this research, for such two types of "hard" discrete optimization problems, we designed efficient algorithms which are theoretically evaluated by the worst case possible relative errors over all possible instances of the problems.