Lattice Algorithms and Their Applications to Combinatorial Optimization

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

While integer programming problems are known to be hard (NP-hard) in general, there is a great practical need to solve such problems. In the last decade or so, operations researchers have looked at integer programming problems from a computational complexity viewpoint and a polynomial time algorithm was devised for any fixed number of dimensions. The approach involved solving a well-defined problem on lattices and then applying the result to integer programs. A lattice is the set of all integer combinations of a finite set of linearly independent vectors (the finite set of vectors is called a basis of the lattice). These results indicate that a better understanding of lattices could yield important advances in solving combinatorial optimization problems. This research will concentrate on lattices and has two main aims: to devise more efficient algorithms for lattice problems, and to apply these algorithms to solve integer programming and other combinatorial optimization problems.