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


Permutahedron Pn is a polyhedron in the n dimensional space defined by the convex hull of all permutations vectors x(π) = (π(1),π(2), … ,π(n)) ∈ Rn. In this talk, we are concerned with randomized rounding in permutahedron; given a point p ∈ Pn, output a permutation vector X(π) with a probability satisfying that E[X] = ∑π ∈ Sn Pr[X=x(π)] x(π) = p. It is well known that Pn is a base polyhedron of a submodular function, more precisely Pn = {x | ∑i ⊂ I xi ≤ ∑j=1|I| (n+1-j) for any I ⊂ [n], and i ⊂ [n] xi = 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


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


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.


  Payday Loans In Missouri. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.