On the convex hull of multicuts on a cycle

On the convex hull of multicuts on a cycle

0.00 Avg rating0 Votes
Article ID: iaor20103033
Volume: 15
Issue: 2
Start Page Number: 51
End Page Number: 60
Publication Date: Jun 2009
Journal: International Journal of Management Science
Authors:
Abstract:

The minimum multicut problem on a cycle is to find a multicut on an undirected cycle such that the sum of weights is minimized, which is known to be polynomially solvable. This paper shows that there exists a compact polyhedral description of the set of feasible solutions to the problem whose number of variables and constraints is O(ν kappa).

Reviews

Required fields are marked *. Your email address will not be published.