Lexicographic max-ordering optimization for data analysis on graphs

Many problems in applied data- and computer science are naturally formulated as optimization problems. In this paradigm, we solve problems by first formulating a criterion that describes the qualities of a good solution.

We then use various optimization methods to find a solution that is as good as possible according to our chosen criterion.

The ubiquity of this approach to problem solving means that good optimization methods are a key enabling technology in many areas of computer science and its many applications.

In this proposal, we focus on a special class of combinatorial optimization problems, called lexicographic max-ordering (Lex-MO) optimization problems.

Our interest in this class of problems is motivated by a recent discovery made by our team: Many optimization problems that are currently considered infeasible to solve (NP-hard) can be solved in low-order polynomial time if we recast the as Lex-MO problems!

This includes many problems that naturally occur in practical applications.The overall aim of this proposal is to provide a detailed and systematic characterization of the class of Lex-MO optimization problems that can be solved using efficient, low-order polynomial time, algorithms.

This project would lead to new algorithms, methods, and insights in combinatorial optimization with a high potential impact on many applied problems in data analysis and computer science.