Thomas Rothvoß

  1. Extended formulations for polygons.

    Authors: Samuel Fiorini, Thomas Rothvoß, Hans Raj Tiwary
    Subjects: Discrete Mathematics
    Abstract

    The extension complexity of a polytope $P$ is the smallest integer $k$ such
    that $P$ is the projection of a polytope $Q$ with $k$ facets. We study the
    extension complexity of $n$-gons in the plane. First, we give a new proof that
    the extension complexity of regular $n$-gons is $O(\log n)$, a result
    originating from work by Ben-Tal and Nemirovski (2001). Our proof easily
    generalizes to other permutahedra and simplifies proofs of recent results by
    Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower
    bound of $\sqrt{2n}$ on the extension complexity of generic $n$-gons.

  2. Edge-Colouring Hypergraphs Properly (Covering with Matchings) or Polychromatically (Packing Covers).

    Authors: David Pritchard, Thomas Rothvoß
    Subjects: Combinatorics
    Abstract

    Let the chromatic index of a hypergraph be the smallest number of colours
    needed to colour the edges such that similarly-coloured edges are disjoint.
    Likewise, let the cover index be the maximum number of colours so that each
    colour class covers all vertices. Trivially the chromatic index is at least the
    maximum degree, and the cover index is at most the minimum degree. We survey
    some classes of structured hypergraphs and ask how far the trivial bounds are
    from tight. We are motivated by a large amount of recent work in this area for
    geometric settings.

  3. Bin Packing via Discrepancy of Permutations.

    Authors: Dömötör Pálvölgyi, Friedrich Eisenbrand, Thomas Rothvoß
    Subjects: Discrete Mathematics
    Abstract

    A well studied special case of bin packing is the 3-partition problem, where
    n items of size >1/4 have to be packed in a minimum number of bins of capacity
    one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a
    suitable LP relaxation for this problem into an integral solution that requires
    at most O(log n) additional bins.

Syndicate content