Matthias Köppe

Dr. Matthias Köppe

orcid

Research Focus & Metrics

Academic Career Length

34Years (1993-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
27 December 2012
Verified
Book
Closed access
JLJesús A. De Loera
Jesús A. De Loera
RHRaymond Hemmecke
Raymond Hemmecke
Matthias KöppeMatthias Köppe
Matthias Köppe

6 November 2009
Verified
Book Chapter
Closed access
PDF file
RHRaymond Hemmecke
Raymond Hemmecke
Matthias KöppeMatthias Köppe
Matthias Köppe
JLJon Lee
Jon Lee
RWRobert Weismantel
Robert Weismantel

1 January 2008 in The Electronic Journal of Combinatorics
Verified
Journal Article
Open access
PDF file
Matthias KöppeMatthias Köppe
Matthias Köppe
SVSven Verdoolaege
Sven Verdoolaege
Computations with Barvinok's short rational generating functions are traditionally being performed in the dual space, to avoid the combinatorial complexity of inclusion–exclusion formulas for the intersecting proper faces of cones. We prove that, on the level of indicator functions of polyhedra, there is no need for using inclusion–exclusion formulas to account for boundary effects: All linear identities in the space of indicator functions can be purely expressed using partially open variants of the full-dimensional polyhedra in the identity. This gives rise to a practically efficient, parametric Barvinok algorithm in the primal space.

18 February 2010 in Journal of Optimization Theory and Applications
Verified
Journal Article
Open access
PDF file
Matthias KöppeMatthias Köppe
Matthias Köppe
MQM. Queyranne
M. Queyranne
CRC. T. Ryan
C. T. Ryan
We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.

14 July 2010 in Mathematics of Computation
Verified
Journal Article
Closed access
PDF file
VBVelleda Baldoni
Velleda Baldoni
NBNicole Berline
Nicole Berline
JLJesus De Loera
Jesus De Loera
Matthias KöppeMatthias Köppe
Matthias Köppe
MVMichèle Vergne
Michèle Vergne
This paper starts by settling the computational complexity of the problem of integrating a polynomial function f f over a rational simplex. We prove that the problem is N P \mathrm {NP} -hard for arbitrary polynomials via a generalization of a theorem of Motzkin and Straus. On the other hand, if the polynomial depends only on a fixed number of variables, while its degree and the dimension of the simplex are allowed to vary, we prove that integration can be done in polynomial time. As a consequence, for polynomials of fixed total degree, there is a polynomial time algorithm as well. We explore our algorithms with some experiments. We conclude the article with extensions to other polytopes and discussion of other available methods.

1 January 2007 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
Matthias KöppeMatthias Köppe
Matthias Köppe
We introduce variants of Barvinok’s algorithm for counting lattice points in polyhedra. The new algorithms are based on irrational signed decomposition in the primal space and the construction of rational generating functions for cones with low index. We give computational results that show that the new algorithms are faster than the existing algorithms by a large factor.