Loading Events

« All Events

  • This event has passed.

ALOP Colloquium with Stefan Weltge

December 4 / 12:00 - 14:00

On Wednesday, December 4, 2019 at 12:00 c.t., Prof. Dr. Stefan Weltge, Assistant Professor at Technical University Munich (TUM) will present his recent work entitled

Persistency of Linear Programming Relaxations for Stable Set

Abstract:

 

The Nemhauser-Trotter theorem states that the standard linear programming (LP) relaxation for the stable set problem has a remarkable property, also known as the (weak) persistency property:  for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values.

While the standard LP is defined by only non-negativity and edge constraints, a variety of stronger LP relaxations have been studied and one may wonder whether any of them is persistent as well. We show that any stronger family of LP relaxations that satisfies mild conditions cannot be persistent on all graphs, unless it is always equal to the stable-set polytope.

This is recent joint work with Elisabeth Rodríguez-Heck, Karl Stickler and Matthias Walter.  

 

The presentation will take place in E 51.

Coffee will be served.

Details

Date:
December 4
Time:
12:00 - 14:00
Event Category:

Organizer

RTG ALOP at Trier University
Phone:
0651-2013461
Email:
ALOP@uni-trier.de

Venue

Trier University E Building
Universitätsring 15
Trier, 54296 Germany
+ Google Map


ALOP