Projects Seminar

The final project presentations will take place on Tuesday, December 18, 10-12h30, in MA B1 524.
The presentations should last up to 30 min (including questions).

The schedule is as follows:

Matthieu Haeberle: On Lattices with Bounded Orthogonality Defect

Given a lattice and a target vector in space, the Closest Vector Problem aks for a lattice vector minimizing the distance to the target vector.

In general, this problem is NP-hard and yet surprisingly easy to solve when the basis is orthogonal. This leads us to study bases that are almost orthogonal, hoping to solve CVP in a more efficient way.

Caroline Andenmatten: The flatness constant of the square and the cube

The presentation will be about upper bounds of the lattice width of lattice-free parallelograms and parallelepipeds. These upper bounds are called the flatness constants. I will present the tight bound for parallelograms and then discuss an approach for parallelepipeds.

Daria Izzo: Matroids and minimal matchings

The tropical determinant is defined similarly to the classic determinant but replacing multiplications by sums and sums by the minimum operator. If the tropical determinant on a square submatrix induced by a subset of columns is obtained only by one permutation this subset of columns is called a tropically regular set. Our main question is to verify for which matrices its tropically regular sets form a set of bases of a matroid.

I will show how the subsets of columns can be represented by bipartite graphs and minimal weight matchings. Moreover I will show how the main problem can be reduced to a calculation with the classic determinant.

Jonas Racine: Finding wagon circulations in practice

In the context of freight transportation by rail, it is of interest to compute periodic wagon circulations that satisfy as much demand as possible. We will recall how this problem can be modelled as a flow problem and use this practical example to introduce convex cost flow problems and the algorithms associated to them.