Monday, May 23, 2015
Freie Universität Berlin
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
Diversity maximization is an important concept in information retrieval,
computational geometry and operations research. Usually, it is a variant of the following
problem: Given a ground set, constraints, and a function $f(\cdot)$ that measures
diversity of a subset, the task is to select a feasible subset $S$ such that $f(S)$ is
maximized. The \emph{sum-dispersion} function $f(S) = \sum_{x,y \in S} d(x,y)$, which is
the sum of the pairwise distances in $S$, is in this context a prominent diversification
measure. The corresponding diversity maximization is the \emph{max-sum} or \emph{sum-sum
diversification}. Many recent results deal with the design of constant-factor
approximation algorithms of diversification problems involving sum-dispersion function
under a matroid constraint. In this paper, we present a PTAS for the max-sum
diversification problem under a matroid constraint for distances $d(\cdot,\cdot)$ of
\emph{negative type}. Distances of negative type are, for example, metric distances
stemming from the $\ell_2$ and $\ell_1$ norm, as well as the cosine or spherical, or
Jacquard distance which are popular similarity metrics in web and image search.
Joint work with A. Cevallos and R. Zenklusen
Colloquium - 16:00
Abstract:
Colorings of graphs represented by geometric objects have been studied
since the 1960s for purely aesthetic as well as practical reasons. In
particular, geometric representations provide natural examples of
classes of graphs that are X-bounded (near-perfect), which means that
their chromatic number is bounded by a function of their clique
number. It was conjectured for many years that all classes of
geometric intersection graphs in the plane are X-bounded. However, in
2012, Pawlik et al. disproved this conjecture presenting a
construction of triangle-free segment intersection graphs with
arbitrarily large chromatic number. This result stimulated further
research aimed at understanding how the chromatic number of geometric
intersection graphs behaves under the assumption that the clique
number is bounded.
After introducing basic problems and results on colorings of geometric
intersection graphs, I will briefly discuss methods applied to obtain
lower and upper bounds on their chromatic number, and connections to
other combinatorial problems of not necessarily geometric nature. I
will also report on a very recent result, joint with Alexandre Rok
(Ben-Gurion University of the Negev): the class of intersection graphs
of curves in the plane each crossing a fixed line at least once and at
most t times is X-bounded, for every t.