[home] - [up] |

Lectures and Colloquia during the semester

Freie Universität Berlin - Institut für Informatik

Takustraße 9

14195 Berlin

Room 005 - map -

*Abstract: *
Consider a weighted hypergraph *G = (V, E)*, where we have a real-valued
weight function *A: V -> [0,1)* defined by *A(v_i) = a_i * for
each
*v_i in V ={v_1, v_2,...,v_n}*.
For each *e in E*, let *A(e)* be the sum of weights of the vertices of
*e*.
A rounding *B* is a binary function from *V* to *{0,1}*.
The *L_p*-discrepancy (in precise, inhomogeneous discrepancy)
of the rounding *B* is defined by
* [ sum_{e in E} |A(e)-B(e)|^p ]^{1/p}*.
The *L_infty*-discrepancy is defined by
* max_{e in E} |A(e) - B(e)|*.

In this talk, we discuss the discrepancy of a rounding for
some geometric hypergraphs.
An *interval hypergraph* is a hypergraph where
each hyperedge corresponds to a subinterval of the index *[1,n]*.
Its rounding is called a *sequence rounding*, and
related to digitizing a stream of analogue data.
We can also organize the vertices into an *N x N* matrix where *N^2
= n*,
and consider hypergraphs whose hyperedges correspond to well shaped
regions in the matrix (regarded as a two-dimensional grid array).
A rounding for such a hypergraph is called a *matrix rounding*,
and related to digital halftoning, which is a central topic in image
processing.

A rounding is called a *global rounding* if its *L_infty*
discrepancy
is strictly less than *1*.
If the hypergraph is unimodular, it is well-known that
there always exists a global rounding.
First, we discuss some hypergraphs for which we have nontrivial upper
bounds of the number of global roundings.
We show that there exists at most *n+1* global sequence roundings for
a given input *A* if the hypergraph consists of hyperedges corresponding
to all the subintervals of *[1,n]*.
This fact can be generalized to the arboreal hypergraph corresponding to
set of all paths in a tree. We also discuss combinatorial structure of
the
set of global roundings of some hypergraphs.

Next, we consider the matrix-rounding problem, where each hyperedge
corresponds
to a *2* by *2* rigid submatrix. We show that it is NP hard to decide
whether
the *L_infty*-discrepancy of the optimal rounding is at most *1/2* or
at least *1*.
Also, we show that there always exists a rounding whose *L_infty*
discrepancy is at most
*5/3*, although we do not have any nontrivial lower bound.

Finally, we give an efficient algorithm to compute the rounding
minimizing
the *L_p*-discrepancy for a given interval hypergraph.
We also define a class of hypergraphs corresponding to matrix roundings
for which we have efficient polynomial time algorithms, and report some
experimental results.

**Colloquium - 16:00**

*Abstract: *
Suppose that we are given a graph, a metric given by edge weights
and a set *T* of required vertices called
*terminals*. The *Steiner minimum tree problem* consists of finding a
tree of minimum weight that spans all vertices in *T*.

We show that it is not possible to approximate the Steiner minimum tree problem within
*136/135* unless *co-RP = NP*.
This improves the currently best known lower bound by about a factor of *3*.
The reduction is from H\aa stad's
nonapproximability result for maximum satisfiability of
linear equation modulo *2*. The improvement on the nonapproximability ratio is mainly
based on the fact that our reduction does not use variable gadgets.
This idea was introduced by Papadimitriou and Vempala.

[home] - [up] - [top]