Pricing problems: inverse discrete optimization

Témavezető: Frank András
ELTE TTK, Matematikai Intézet, Operációkutatási Tanszék.
email: andras.frank@ttk.elte.hu

Projekt leírás

A typical problem in discrete optimization is to find a best member of a given set of combinatorial objects. For example, Dijkstra's algorithm computes a cheapest st-path of a digraph, or the Hungarian method computes a maximum weight perfect matching of a bipartite graph.

In the inverse (or pricing) problems the situation is just the opposite: for a specified input object (e.g., a given st-path or a perfect matching), we are interested in finding the "best" cost- (or weight-) function for which the input object is optimal. For example, how should one minimally modify an input weight-function so that the input perfect matching become a maximum weight perfect matching?

Although there is a rather general min-max formula for the optimal pricing, in several special cases no polynomial algorithm has been yet worked out. The major goal of the present project is to explore special cases for which such an algorithm can be developed.

The topic is suggested for those who feel close to the area of discrete optimization (network flows, matchings, trees, paths), have an affinity to serious challenges, and are ready to delve into a new exciting area.

Előfeltételek

basic knowledge in discrete optimization (graph theoretic algorithms, min-max theorems, linear programming)

Hivatkozások