KAIST Discrete Math Seminar

During the last decade, inverse combinatorial optimization problems have found an increased interest in the optimization community. Whereas an optimization problem asks for a feasible solution with minimum or maximum objective function value, inverse optimization problems are defined with a feasible solution, and aim to perturb as little as possible the parameters (costs, profits, etc.) of the problem so that the given solution becomes optimum in the new instance. In this talk, we introduce some generalized inverse combinatorial problems, and investigate inverse chromatic number problems in permutation graphs and interval graphs.