Rade T. Zivaljevic - Mathematical Institute SANU, Belgrade

Groupoids in Geometric Combinatorics

Abstract: The introduction of groups of projectivities (M. Joswig 2002) and the solution of the Lovasz conjecture (E. Babson and D. Kozlov 2005), together served as a motivation for introducing the language and the methods of the theory of groupoids in combinatorics. We review the foundations of this theory and discuss the possibilities arising from the systematic use of the concepts like "holonomy", "parallel transport", "bundles", "combinatorial curvature" etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects.

The applications include the definition of a new, holonomy-type invariant for cubical complexes, leading to a combinatorial "Theorema Egregium" for these objects, and an extension of Babson-Kozlov-Lovasz graph coloring results to more general statements about non-degenerate maps (colorings) of simplicial complexes.

Colloquium - 16:00

Alberto Ceselli -Universitá degli Studi di Milano

Penalized and ordered knapsack problems

Abstract: In this talk I discuss two strictly related variations of the 0-1 knapsack (KP), both arising as subproblems in column generation algorithms for packing problems.

First, I consider a penalized knapsack problem (PKP), in which each item has a profit, a weight and a penalty. A subset of items has to be selected such that the sum of their weights does not exceed a given capacity and the objective function to be maximized is the sum of the profits of the selected items minus the largest penalty associated with the selected items. I present an integer linear programming formulation and I describe an exact optimization algorithm exploiting reduction, bounding and domination criteria.

Then, I extend these methods to the optimization of an open-end variation of the KP, in which the items are presented in a given order, and the last selected item is allowed to violate the capacity constraint.

Finally, I report experimental results on randomly generated instances of different size with different types of correlation between data. This analysis shows that our algorithms are two orders of magnitude faster than a state-of-the-art general purpose solver.

(Joint work with G.Righini)