## Invited Session Mon.1.MA 004

#### Monday, 10:30 - 12:00 h, Room: MA 004

**Cluster 11: Integer & mixed-integer programming** [...]

### Advances in integer programming

**Chair: Shmuel Onn**

**Monday, 10:30 - 10:55 h, Room: MA 004, Talk 1**

**Antoine Deza**

Combinatorial, computational, and geometric approaches to the colourful simplicial depth

**Coauthors: Frédéric Meunier, Tamon Stephen, Feng Xie**

**Abstract:**

In statistics, there are several measures of the depth of a point *p* relative to a fixed set *S* of sample points in dimension *d*. One of the most intuitive is the simplicial depth of *p* introduced by Liu (1990), which is the number of simplices generated by points in *S* that contain *p*. Obtaining a lower bound for the simplicial depth is a challenging problem. Carathéodory's Theorem can be restated as: The simplicial depth is at least *1* if *p* belongs to the convex hull of *S*. Bárány (1982) showed that the simplicial depth is a least a fraction of all possible simplices generated from *S*. Gromov (2010) improved the fraction via a topological approach. Bárány's result uses a colourful version of the Carathéodory's theorem leading to the associated colourful simplicial depth. We present recent generalizations of the Colourful Carathéodory's theorem due to Arocha et al. and Homlsen et al. and our strengthening of these. We provide a new lower bound for the colourful simplicial depth improving the earlier bounds of Bárány & Matoušek and of Stephen & Thomas. Computational approaches for small dimension and the colourful linear programming feasibility problem introduced by Bárány & Onn are discussed.

**Monday, 11:00 - 11:25 h, Room: MA 004, Talk 2**

**Justo Puerto**

Ordered weighted average optimization of combinatorial problems

**Abstract:**

This talk addresses a class of combinatorial optimization models that include among others, bottleneck, *k*-centrum, general balanced, lexicographic, ordered median and universal optimization. These problems have been analyzed under different names for different authors in the last years (Calvete and Mateos (1998), De la Croce et al. (1999), Lee (1992), Nickel and Puerto (2005), Puerto and Tamir (2005), Punnen and Aneja (1996, 2004), Turner and Hamacher (2011), Turner et al. (2011)). We study the common framework that underlines those models, present different formulations as integer programs and study their relationships and reinforcements. This approach leads to a branch and cut algorithm applicable to he general problem which is effective up to median size instances. For some specific cases we also analyze specific properties leading to polynomial time combinatorial algorithms.

**Monday, 11:30 - 11:55 h, Room: MA 004, Talk 3**

**Matthias Köppe**

A discretization-free FPTAS for polynomial optimization over the mixed-integer points in a class of polytopes of varying dimension

**Coauthors: Nicole Berline, Michèle Vergne**

**Abstract:**

We present a new fully polynomial-time approximation scheme for the

problem of optimizing non-convex polynomial functions over the

mixed-integer points of a polytope of fixed dimension. This improves

upon earlier work that was based on discretization [De Loera,

Hemmecke, Köppe, Weismantel, FPTAS for optimizing polynomials~ … ,

Math. Prog. Ser. A 118 (2008), 273-290]. The algorithm also extends

to a class of problems in varying dimension.

The algorithm is based on the study of intermediate sums,

interpolating between integrals and discrete sums, initiated by

A. Barvinok [2006] and continued by Baldoni, Berline, De Loera, Köppe,

Vergne [Computation of the highest coefficients~ … ,

Found. Comput. Math. 2012] and Baldoni, Berline, Köppe, Vergne

[Intermediate sums on polyhedra~ … , Mathematika 2012]. For a given

polytope *P* with facets parallel to rational hyperplanes and a rational

subspace *L*, we integrate a given polynomial function *h* over all

lattice slices of the polytope *P* parallel to the subspace *L* and sum up

the integrals.

This is the culmination of an effort to extend the efficient

theory of discrete generating functions to the mixed-integer case.