## Faster Separation of wheel inqualities for stable set polytopes |
Back |

Abstract: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). http://www.mathematik.uni-trier.de/~devries/ |
Type of Seminar:Optimization and Applications Seminar |

Speaker:Prof. Dr. Sven de Vries University of Trier, Germany | |

Date/Time:May 10, 2010 16:30 | |

Location:HG G 19.1, Rämistrasse 101 | |

Contact Person:Prof. J. Lygeros | |

No downloadable files available. | |

Biographical Sketch:http://www.mathematik.uni-trier.de/~devries/cv |