S
Forum 'Annonces' - Sujet créé le 2010-02-22
Nous avons le plaisir de vous inviter à une séminaire "Inverse Combinatorial Optimization" co-organisé par l'Université Paris 1 et l'ESSEC Business School
Mercredi 3 mars– 9 :00 – 12 :30
Inverse Combinatorial Optimization
Lieu: Maison des Sciences Economiques, 106-112 Boulevard de l'Hôpital, 715013 Paris. 6ième étage
Metro: Campo-Formio ou Place d'Italie
Programme:
9: 00 – 9:30: Accueil
9: 30 – 10:20
INVERSE LOCATION PROBLEMS: THE INVERSE FERMAT-WEBER PROBLEM AND THE INVERSE
1-CENTER PROBLEM ON A TREE.
Rainer E. Burkard, Technische Universitaet Graz, Austria
10:30-11:20
INVERSE MINIMUM FLOW PROBLEM UNDER L-infty NORM,
Adrian Deaconu and Eleonor Ciurea, University Transylvania of Brasov, Romania
11:30 – 12:20
ON SOME INVERSE MATCHING PROBLEMS
Laurent Alfandari, ESSEC Business School, Paris, France, Marc Demange, ESSEC Business School Bucharest, Romania and Jérôme Monnot, Université Paris-Dauphine, France
---------------------------------------------------------------------------------------------------- ----------------
Résumés:
INVERSE LOCATION PROBLEMS: THE INVERSE FERMAT-WEBER PROBLEM AND THE INVERSE
1-CENTER PROBLEM ON A TREE.
Rainer E. Burkard, Technische Universitaet Graz, Austria
Abbstract:
The task of an inverse location problem is to change the parameters of a
given location problem at minimum cost such that a given solution becomes
optimal. We shortly survey inverse median and center problems and explain
in greater detail polynomial solution algorithms for the inverse Fermat-Weber
problem and for the inverse 1-center location problem on trees. In both cases
optimality conditions for the underlying location problem play a crucial role
for the development of solution procedures.
INVERSE MINIMUM FLOW PROBLEM UNDER Linfty NORM,
Adrian Deaconu and Eleonor Ciurea, University Transylvania of Brasov, Romania
Abstract: The inverse minimum flow problem consists in modifying the capacities of the arcs from a network so that a given feasible flow becomes a minimum flow and the maximum change to the capacities on arcs is minimum. A strongly polynomial algorithm for solving this problem is given.
ON SOME INVERSE MATCHING PROBLEMS
Laurent Alfandari, ESSEC Business School, Paris, France, Marc Demange, ESSEC Business School Bucharest, Romania and Jérôme Monnot, Université Paris-Dauphine, France
Abstract: We consider the Inverse Maximum Weighted Matching Problem(under L-1 norm) that aims to modify the weight-system so that a fixed matching becomes optimal. If weights are of real values, then the problem is polynomial. We consider the Boolean constrained case aiming to add/remove the minimum number of edges in a graph so that a fixed matching becomes optimal. We show that it is NP-hard in general graphs and polynomial in bipartite graphs, while a bi-valued and integral versions are hard, even in bipartite graphs. We also study the problem where the fixed matching is supposed to become only k-optimal in the modified instance.
Pour tout renseignement complémentaire, vous pouvez contacter Marc Demange (demange@essec.edu)
Mercredi 3 mars– 9 :00 – 12 :30
Inverse Combinatorial Optimization
Lieu: Maison des Sciences Economiques, 106-112 Boulevard de l'Hôpital, 715013 Paris. 6ième étage
Metro: Campo-Formio ou Place d'Italie
Programme:
9: 00 – 9:30: Accueil
9: 30 – 10:20
INVERSE LOCATION PROBLEMS: THE INVERSE FERMAT-WEBER PROBLEM AND THE INVERSE
1-CENTER PROBLEM ON A TREE.
Rainer E. Burkard, Technische Universitaet Graz, Austria
10:30-11:20
INVERSE MINIMUM FLOW PROBLEM UNDER L-infty NORM,
Adrian Deaconu and Eleonor Ciurea, University Transylvania of Brasov, Romania
11:30 – 12:20
ON SOME INVERSE MATCHING PROBLEMS
Laurent Alfandari, ESSEC Business School, Paris, France, Marc Demange, ESSEC Business School Bucharest, Romania and Jérôme Monnot, Université Paris-Dauphine, France
---------------------------------------------------------------------------------------------------- ----------------
Résumés:
INVERSE LOCATION PROBLEMS: THE INVERSE FERMAT-WEBER PROBLEM AND THE INVERSE
1-CENTER PROBLEM ON A TREE.
Rainer E. Burkard, Technische Universitaet Graz, Austria
Abbstract:
The task of an inverse location problem is to change the parameters of a
given location problem at minimum cost such that a given solution becomes
optimal. We shortly survey inverse median and center problems and explain
in greater detail polynomial solution algorithms for the inverse Fermat-Weber
problem and for the inverse 1-center location problem on trees. In both cases
optimality conditions for the underlying location problem play a crucial role
for the development of solution procedures.
INVERSE MINIMUM FLOW PROBLEM UNDER Linfty NORM,
Adrian Deaconu and Eleonor Ciurea, University Transylvania of Brasov, Romania
Abstract: The inverse minimum flow problem consists in modifying the capacities of the arcs from a network so that a given feasible flow becomes a minimum flow and the maximum change to the capacities on arcs is minimum. A strongly polynomial algorithm for solving this problem is given.
ON SOME INVERSE MATCHING PROBLEMS
Laurent Alfandari, ESSEC Business School, Paris, France, Marc Demange, ESSEC Business School Bucharest, Romania and Jérôme Monnot, Université Paris-Dauphine, France
Abstract: We consider the Inverse Maximum Weighted Matching Problem(under L-1 norm) that aims to modify the weight-system so that a fixed matching becomes optimal. If weights are of real values, then the problem is polynomial. We consider the Boolean constrained case aiming to add/remove the minimum number of edges in a graph so that a fixed matching becomes optimal. We show that it is NP-hard in general graphs and polynomial in bipartite graphs, while a bi-valued and integral versions are hard, even in bipartite graphs. We also study the problem where the fixed matching is supposed to become only k-optimal in the modified instance.
Pour tout renseignement complémentaire, vous pouvez contacter Marc Demange (demange@essec.edu)