Monday, 15:15 - 15:40 h, Room: H 3012


Matthew Oster
A branch and cut algorithm for solving capacitated max k-cut with an application in scheduling

Coauthor: Jonathan Eckstein


We model the scheduling of a symmetric multi-track conference as a capacitated version of the combinatorial optimization problem known as Maximum k-Cut (MKC). We solve this NP-hard problem to optimality within a branch-and-bound framework equipped with a semidefinite programming relaxation of MKC, enhanced with triangle and clique cuts, as well as new problem-specific cuts (e.g., what we call star-capacity cuts, total-capacity cuts, etc.). We also introduce a new heuristic for generating feasible solutions at most tree nodes. Test results for small to moderate-sized conferences will be discussed for both serial and parallel implementations of our algorithm.


Talk 1 of the contributed session Mon.3.H 3012
"Scheduling II" [...]
Cluster 2
"Combinatorial optimization" [...]


  personal loan . In this section we give only a brief summary recommendation for admission of Cheap Levitra. Full information can be found in the instructions for receiving medications with vardenafil.