Journal of Combinatorial Optimization