[home] - [up]

Lectures and Colloquia during the semester

December 3, 2001

Freie Universität Berlin - Institut für Informatik
Takustraße 9
14195 Berlin
Room 005           - map -
Lecture - 14:15

### Combinatorics and algorithms on rounding sequences and matrices

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

### On the Approximability of the Steiner Tree Problem

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]