Soutenance de th
Forum 'Annonces' - Sujet créé le 2010-02-25
Bonjour,
J'ai le plaisir de vous annoncer ma soutenance de thèse, préparée sous la direction de Marc Demange.
Yerim Chung
Date de la soutenance:
le 2 mars à 15h30 à la MSE, 106-112 bd. de l'Hôpital 75013 Paris
Salle du 6ème étage
Titre:
Inverse combinatorial problems and applications
Résumé:
Inverse combinatorial optimization problems have attracted an attention among the operations research community during the last two decades. Given an instance of a combinatorial optimization problem, defined by a weight system (costs, profits, etc.), and a feasible solution, it is to perturb as little as possible the weight system so that the fixed solution becomes optimum in the new instance. A variety of inverse combinatorial optimization problems have been studied by many researchers. However, there are fairly few studies on inverse versions of NP-hard problems.
In our work, we consider generalized inverse combinatorial optimization problems. In fact, we generalize usual inverse combinatorial optimization problems by adding some weight constraints that the original and/or new weight system should satisfy. ``Weight-constrained inverse combinatorial optimization problems'' allow us to define the inverse version of non-weighted combinatorial optimization problems by imposing the boolean weight constraints.
We also introduce some variants of inverse combinatorial optimization, namely, ``inverse problems against a specific algorithm'' and ``inverse number problems''. For the former, we specify an algorithm (optimal or not) as well as a solution, and find a minimum modification of a given instance such that the fixed solution can be selected by the given algorithm. Inverse number problems are defined by specifying a target solution value instead of a target solution. The objective is to modify as little as possible the given instance so that the optimal solution value of the new instance is equal to the fixed value.
We study inverse problems of well-known NP-hard problems, such as the maximum stable set problem, the minimum traveling salesman problem, the minimum vertex coloring problem and the minimum bin-packing problem. The main purpose of this work is to study the complexity status and the approximation behavior of these inverse combinatorial problems.
Membres du Jury:
Nadia brauner Vettier
Rainer E. Burkard
Eleonor Ciurea
Marc Demange
Michel Grabisch
Jérôme Monnot
J'ai le plaisir de vous annoncer ma soutenance de thèse, préparée sous la direction de Marc Demange.
Yerim Chung
Date de la soutenance:
le 2 mars à 15h30 à la MSE, 106-112 bd. de l'Hôpital 75013 Paris
Salle du 6ème étage
Titre:
Inverse combinatorial problems and applications
Résumé:
Inverse combinatorial optimization problems have attracted an attention among the operations research community during the last two decades. Given an instance of a combinatorial optimization problem, defined by a weight system (costs, profits, etc.), and a feasible solution, it is to perturb as little as possible the weight system so that the fixed solution becomes optimum in the new instance. A variety of inverse combinatorial optimization problems have been studied by many researchers. However, there are fairly few studies on inverse versions of NP-hard problems.
In our work, we consider generalized inverse combinatorial optimization problems. In fact, we generalize usual inverse combinatorial optimization problems by adding some weight constraints that the original and/or new weight system should satisfy. ``Weight-constrained inverse combinatorial optimization problems'' allow us to define the inverse version of non-weighted combinatorial optimization problems by imposing the boolean weight constraints.
We also introduce some variants of inverse combinatorial optimization, namely, ``inverse problems against a specific algorithm'' and ``inverse number problems''. For the former, we specify an algorithm (optimal or not) as well as a solution, and find a minimum modification of a given instance such that the fixed solution can be selected by the given algorithm. Inverse number problems are defined by specifying a target solution value instead of a target solution. The objective is to modify as little as possible the given instance so that the optimal solution value of the new instance is equal to the fixed value.
We study inverse problems of well-known NP-hard problems, such as the maximum stable set problem, the minimum traveling salesman problem, the minimum vertex coloring problem and the minimum bin-packing problem. The main purpose of this work is to study the complexity status and the approximation behavior of these inverse combinatorial problems.
Membres du Jury:
Nadia brauner Vettier
Rainer E. Burkard
Eleonor Ciurea
Marc Demange
Michel Grabisch
Jérôme Monnot