University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Counting vertices of integral polytopes defined by facets

Counting vertices of integral polytopes defined by facets

Add to your list(s) Download to your calendar using vCal

  • UserMark Jerrum, London
  • ClockThursday 10 November 2022, 15:00-16:00
  • HouseLTC.

If you have a question about this talk, please contact Johannes Carmesin.

I’ll address the computational complexity of counting vertices of an integral polytope defined by a system of linear inequalities. The focus will be on polytopes with small integer vertices, particularly 0/1 and half-integral polytopes. The geometric approach to combinatorial optimisation, as explored in Schrijver’s 3-volume monograph, provides plentiful examples of these. The complexity of exact counting is pretty well understood, so I’ll concentrate on approximate counting with guaranteed error bounds. The complexity landscape is only partially understood, but there appear to be natural examples that are neither in P nor NP-hard. No knowledge of complexity theory beyond P and NP will be assumed.

This is joint work with Heng Guo (Edinburgh)

This talk is part of the Combinatorics and Probability seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.