## Invited Session Mon.2.H 3008

#### Monday, 13:15 - 14:45 h, Room: H 3008

**Cluster 2: Combinatorial optimization** [...]

### Discrete structures and algorithms I

**Chair: Satoru Fujishige**

**Monday, 13:15 - 13:40 h, Room: H 3008, Talk 1**

**Shuji Kijima**

Efficient randomized rounding in permutahedron

**Abstract:**

Permutahedron *P*_{n} is a polyhedron in the *n* dimensional space defined by the convex hull of all permutations vectors *x(π) = (π(1),π(2), … ,π(n)) ∈ ***R**^{n}. In this talk, we are concerned with randomized rounding in permutahedron; given a point *p ∈ P*_{n}, output a permutation vector *X(π)* with a probability satisfying that **E***[X] = ∑*_{π ∈ Sn} Pr*[X=x(π)] x(π) = p*. It is well known that *P*_{n} is a base polyhedron of a submodular function, more precisely *P*_{n} = {x | ∑_{i ⊂ I} x_{i} ≤ ∑_{j=1}^{|I|} (n+1-j) for any * I ⊂ [n], * and * ∑*_{i ⊂ [n]} x_{i} = n(n+1)/2}. In this talk, we present an algorithm for randomized rounding in permutahedron, with *O(n **log* n) time using *O(n)* space. We also explain an extension to a base polyhedron of an arbitrary cardinality based submodular function.

**Monday, 13:45 - 14:10 h, Room: H 3008, Talk 2**

**Júlia Pap**

Characterizing and recognizing generalized polymatroids

**Coauthors: András Frank, Tamás Király, David Pritchard**

**Abstract:**

Generalized polymatroids are a family of polyhedra with several nice properties and applications. A main tool used widely in the literature is that generalized polymatroids can be described by a linear system whose dual can be uncrossed: there is an optimal dual solution with laminar support. We make this notion of "total dual laminarity'' explicit and show that the polyhedra described by such systems are always generalized polymatroids. We also show that for a full-dimensional generalized polymatroid every describing system is totally dual laminar. Using these we give a polynomial-time algorithm to check whether a given linear program defines a generalized polymatroid, and whether it is integral if so. Additionally, whereas it is known that the intersection of two integral generalized polymatroids is integral, we show that no larger class of polyhedra satisfies this property.

**Monday, 14:15 - 14:40 h, Room: H 3008, Talk 3**

**Jens Massberg**

Dual consistency and cardinality constrained polytopes

**Coauthor: Satoru Fujishige**

**Abstract:**

We introduce a concept of dual consistency of systems of linear inequalities with full generality.

We show that a cardinality constrained polytope is represented by a certain system of linear inequalities if and only if the systems of

linear inequalities associated with the cardinalities are dual consistent.

Typical dual consistent systems of inequalities are those which

describe polymatroids, generalized polymatroids, and dual greedy polyhedra with certain choice functions.

We show that the systems of inequalities for cardinality-constrained

ordinary bipartite matching polytopes are not dual consistent in general, and give additional inequalities to make them dual consistent.

Moreover, we show that ordinary systems of inequalities for the

cardinality-constrained (poly)matroid intersection are not dual consistent, which disproves a conjecture of Maurras, Spiegelberg, and Stephan about a linear representation of the cardinality-constrained polymatroid intersection.