Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Faster Separation of wheel inqualities for stable set polytopes

A stable set in a graph G is a set of pairwise nonadjacent vertices. The problem of fi nding a maximum weight stable set is one of the most basic NP-hard problems. An important approach to this problem is to formulate it as the problem of optimizing a linear function over the convex hull STAB(G) of incidence vectors of stable sets. Then one has to solve separation problems over it. Cheng and Cunningham (1997) introduced the wheel inequalities and presented an algorithm for their separation using time O(n4) for a graph with n vertices and m edges. We present a new separation algorithm running in O(mn2 + n3 log n).
Type of Seminar:
Optimization and Applications Seminar
Prof. Dr. Sven de Vries
University of Trier, Germany
May 10, 2010   16:30

HG G 19.1, Rämistrasse 101
Contact Person:

Prof. J. Lygeros
No downloadable files available.
Biographical Sketch: