Further talks

×

Modal title

Modal content

Spring Semester 2017

Date / Time

Speaker

Title

Location

18 August 2017
14:00-15:00

Dr. Matthias Walter
RWTH Aachen

Details

IFOR talks

Title	Solving Bulk-Robust Assignment Problems to Optimality
Speaker, Affiliation	Dr. Matthias Walter, RWTH Aachen
Date, Time	18 August 2017, 14:00-15:00
Location	HG G 19.1
Abstract	We consider the bulk-robust assignment problem in which we are given a bipartite graph, edge costs, an integer k and a list of failure (edge) sets. The goal is to find minimum-cost subset of edges such that after the removal of any failure set, the remaining subgraph still contains a matching of size k. Recent results are approximation algorithms for the case (a) in which failures consist of single edges and the case (b) in which the edges incident to a vertex are removed at a time. We discuss a straight-forward integer programming model, improve the tractability of its LP relaxation and present cutting planes that are very strong for case (a). Preliminary computational results for solving these problems to optimality are presented. They indicate effectiveness for such structured instances, whereas the LP relaxations for instances with random failure sets are rather weak.

Solving Bulk-Robust Assignment Problems to Optimalityread_more

Notes: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archive: undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined undefined