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.
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.
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.