Algorithmen, Struktur, Zufall - Hauptseite Algorithmen, Struktur, Zufall

Berlin-Poznan Seminar / ASZ Workshop 2008

Humboldt-Universität zu Berlin, 20.-21. Juni 2008

Zeitplan:

Freitag, 20. Juni 2008
14:00 Eröffnung
14:15 Jeong Han Kim Optimal Query Complexity Bounds for Finding Graphs
15:00 Florian Pfender A Turan type theorem for multipartite graphs
15:30 Oleg Pikhurko Game chromatic index of graphs with given restrictions on degrees
16:00 Pause / Promotionsverteidigung Stefan Kirchner Untere Schranken für Steinerbaumalgorithmen und die Konstruktion von Bicliquen in dichten Graphen

Samstag, 21. Juni 2008
8:45 Kaffeepause
9:00 Anand Srivastav Low-Discrepancy Colorings for Arithmetic Progressions
9:30 Bernd Kreuter Patterns and Structures in real markets
10:00 Miroslawa Janczak On a problem of Hilliker and Straus
10:30 Kaffeepause
11:00 Manuel Bodirsky The Product Ramsey Theorem in Constraint Satisfaction Complexity
11:30 Julia Böttcher (Not) separating between sublinear and linear bandwidth and treewidth
12:00 Wojciech Wawrzyniak Distributed packing in planar graphs
12:30 Mittagspause
14:15 Kaffeepause
14:30 Krzysztof Krzywdzinski Distributed constant time algorithm for finding PTAS-approximation of Minimum Spanning Tree in Unit Disc Graphs
15:00 Mariano Zelke Weighted Matching in Streaming Graphs
15:30 Taral Seierstad The differential equations method
16:00 Kaffeepause
16:15 Vojtech Rödl Folkman and Ramsey Numbers
16:45 Anusch Taraz / Mihyun Kang Mathematical history of the Berlin-Poznan seminar
17:45 Abschluss


Alle Vorträge finden statt im 

 Erwin Schrödinger-Zentrum, HU Berlin
 Rudower Chaussee 26,
 12489 Berlin
im Raum 1.306
(Anfahrtsinformationen siehe Lage des ESZ oder im Stadtplan.)

Zusammenfassungen:

Manuel Bodirsky, Ecole Polytechnique

The Product Ramsey Theorem in Constraint Satisfaction Complexity

    In this talk, I show how the product Ramsey theorem can be used jointly with tools from universal algebra to classify the complexity of a large class of computational problems in temporal reasoning. I will also discuss open problems both in constraint satisfaction and Ramsey theory.

Julia Böttcher, TU München

(Not) separating between sublinear and linear bandwidth and treewidth

    Bandwidth and treewidth are well studied graph parameters. While lots of research is dedicated to determining these parameters rather precisely for certain graphs or to graph classes where they are constants, in this talk we will be mainly interested in distinguishing between graph classes where the bandwidth/treewidth is sublinear in the number of vertices and such where these parameters are linear.
    The star shows that in general even trees (i.e. graphs of treewidth 1) can have linear bandwidth. Chung proved that trees with bounded maximum degree however have sublinear bandwidth. This raises the question wether such a result remains true for bounded-degree graphs of bigger treewidth. We answer this question in the affirmative. More generally, we prove that for any hereditary class of bounded-degree graphs the concepts of sublinear bandwidth, sublinear treewidth, the absence of big expanders as subgraphs, and the existence of small separators are equivalent.
    This result implies that planar graphs with bounded maximum degree have sublinear bandwidth. As a consequence we can infer the following embedding result. For each gamma>0 every n-vertex graph (for n sufficiently large) with minimum degree (gamma+3/4)n contains a copy of every bounded-degree planar graph on n vertices.
    Joint work with Klaas Pruessmann, Anusch Taraz, Andreas Würfl.

Miroslawa Janczak, Adam Mickiewicz University Poznan

On a problem of Hilliker and Straus

    For a prime $p$ and a vector $\ha=(\alpha_1,\dots,\alpha_k)\in \Z_p^k$ let $f\left(\ha,p\right)$ be the largest $n$ such that in each set $A\subseteq\Z_{p}$ of $n$ elements one can find $x$ which has a unique representation in the form $x=\a_{1}a_1+\dots +\a_{k}a_k,~a_i\in A$. Hilliker and Straus~\cite{hs} bounded $f\left(\ha,p\right)$ from below by an expression which contained the $L_1$-norm of $\ha$ and asked if there exists a positive constant $c\left(k\right)$ so that $f\left(\ha,p\right)>c\left(k\right)\log p$. In this note we answer their question in the affirmative and show that, for large $k$, one can take $c(k)=O(1/k\log (2k)) $. We also give a lower bound for the size of a set $A\subseteq \Z_{p}$ such that every element of $A+A$ has at least $K$ representations in the form $a+a'$, $a, a'\in A$.

Jeong Han Kim, Yonsei University

Optimal Query Complexity Bounds for Finding Graphs

    We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask sum of weights for the weighted graphs. These types of queries were partially motivated in DNA shotgun sequencing and linkage discovery problem of artificial intelligence.
    For a given unknown weighted graph $G$ with $n$ vertices, $m$ edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of $G$ using $O\left(\frac{m\log{n}}{\log{m}}\right)$ queries of both types provided that $m \geq n^{\epsilon}$ for any constant $\epsilon> 0$. For a graph, it is shown that the same bound holds for all range of $m$.
    This settles a conjecture of Grebinski for finding an unweighte graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions. A similar coin weighing problem is also considered.

Stefan Kirchner, Humboldt-Universität zu Berlin

Untere Schranken für Steinerbaumalgorithmen und die Konstruktion von Bicliquen in dichten Graphen

    Meine Dissertation besteht aus zwei Teilen. Der erste Teil der Arbeit befasst sich mit unteren Schranken für approximative Steinerbaumalgorithmen. Ein Steinerbaum ist ein kürzester Teilgraph, der eine gebenene Teilmenge der Knoten einen Graphen spannt. Das Berechnen eines Steinerbaumes ist ein klassisches NP-schweres Problem, und es existieren mehrere Approximationsalgorithmen, wobei bei den meisten Algorithmen die Approximationsgüte nur durch untere und obere Schranken eingegrenzt werden kann. Für einige dieser Algorithmen werden Instanzen vorgestellt, welche die unteren Schranken verbessern. Für den Relativen Greedy Algorithmus wird außerdem ein Verfahren vorgestellt, mit dem die Güte dieses Algorithmus eingeschränkt auf die Graphenklasse mit k Terminalen auf einen beliebigen Faktor genau bestimmt werden kann.
    Der zweite Teil widmet sich vollständig bipartiten Subgraphen mit gleicher Partitionsgröße, sogenannten balancierten Bicliquen. Seit langem ist bekannt, dass in dichten bipartiten Graphen balancierte Bicliquen mit O(log(n)) Knoten existieren, aber es ist unbekannt, ob und wie diese in polynomieller Zeit konstruiert werden können. Es wird ein polynomieller Algorithmus vorgestellt, der in hinreichend großen dichten bipartiten Graphen eine balancierte Biclique mit O(sqrt(log(n))) Knoten konstruiert.

Bernd Kreuter

Patterns and Structures in real markets

    Patterns and Structures in real markets -- on data mining, multi agent set-ups, the failure of classical probability theory, trading strategies, and many unsolved problems

Krzysztof Krzywdzinski, Adam Mickiewicz University Poznan

Distributed constant time algorithm for finding PTAS-approximation of Minimum Spanning Tree in Unit Disc Graphs

    The Unit Disc Graphs (UDG) is the most natural class of graphs to model wireless ad hoc networks (for example cell phon es networks, wireless sensor networks etc.). The set of vertices of UDG is a set of points on the plane and two vertice s of UDG, $v$ and $w$, are connected by an edge in UDG if and only if they are at the distance at most one in Euklidi an norm ($\left\|v,w\right\| \leq 1$). From application point of view it means that the vertices (cell phones, sensors etc.) are in their communication range. By the weight of an edge $(v,w)$ in UDG we mean the distance between $v$ and $w $ on the plane. Moreover as the weight of a graph (of a subgraph of UDG as well) we define a sum of weights of its edge s.
    One of the most fundamental problems concerning Unit Disc Graphs is finding a Minimum (in terms of its weight) Spannin g Tree of the arbitrarily given Unit Disc Graph G ($MST(G)$). In my presentation I will introduce a new distributed alg orithm, which finds in $O(poly(D))$ synchronous rounds a subgraph $H$ of $G$, which is a good approximation of $MST(G)$ .
    Namely I will prove, that given as an input parameter $D$ and a Unit Disc Graph $G$, the presented algorithm finds in $ O(poly(D))$ synchronous rounds, a subgraph $H$ of $G$ with four following properties:
    $H$ contains one of the $MST(G)$;
    weight of $H$ is $(1+O(1/D))$ approximation of the weight of $MST(G)$;
    $H$ is planar;
    if a shortest path between $v$ and $w$ in $G$ have weight $K$, then the shortest path between $v$ and $w$ in $H$ have weight $O(D)K$.

Florian Pfender, Universität Rostock

A Turan type theorem for multipartite graphs

    Turan's Theorem states that every graph of a certain edge density contains a complete graph K^k and describes the unique extremal graphs. We give a similar Theorem for l-partite graphs. For large l, we find the minimal edge density d_k , such that every l-partite graph whose parts have pairwise edge density greater than d_k contains a K^k . It turns out that d-k = (k-2)/(k-1) for large enough l, refuting a conjecture by Bondy, Shen, Thomasse and Thomassen. We also describe the structure of the extremal graphs.

Oleg Pikhurko, Carnegie Mellon University

Game chromatic index of graphs with given restrictions on degrees

    Given a graph $G$ and an integer $k$, two players alternatively color the edges of $G$ using $k$ colors so that adjacent edges get different colors. The \emph{game chromatic index} $\chi'_g(G)$ is the minimum $k$ for which the first player has a strategy that ensures that all edges of $G$ get colored.
    Lam, Shiu, and Xu and, independently, Bartnicki and Grytczuk asked whether there is a constant $C$ such that $\chi_g'(G)\le \Delta(G)+C$ for every graph $G$. We show that the answer is in the negative. Also, general upper bounds on $\chi'(G)$ in terms of $\Delta(G)$ and $v(G)$ will be discussed.
    This is a joint work with Andrew Beveridge, Tom Bohman, and Alan Frieze.

Taral Seierstad, University of Oslo

The differential equations method

    Wormald's differential equation method is often used to show that parameters defined on random graph processes converge in probability to the solutions of certain differential equations. We show that this method, in many cases, can be extended to show that the parameters converge to a multivariate normal distribution.

Anand Srivastav, Christian-Albrechts-Universität zu Kiel

Low-Discrepancy Colorings for Arithmetic Progressions

    One of the celebrated theorems in discrepancy theory says that the 2-color discrepancy of the hypergraph of arithmetic progressions in the first $n$ integers is $\Theta(n^{1/4})$ (lower bound by Roth (1964), upper bound Matou\v{s}ek, Spencer (1994)). In this talk we give an overview on the discrepancy problem for different kind of arithmetic progressions, among them sums and products, both in the natural numbers as well as in $\mathbb{Z}_{p}$. In particular, we will prove tight bounds for the $c$-color discrepancy function for centered arithmetic progressions in $\mathbb{Z}_{p}$. Here, due to the lack of translation-invariance of the hypergraph Fourier analysis alone does not work, and has to be combined with a new decomposition of such progressions.

Wojciech Wawrzyniak, Adam Mickiewicz University Poznan

Distributed packing in planar graphs

    I'll give an efficient distributed algorithm that finds an almost optimal packing of a graph H in a planar graph G. The algorithm is deterministic and its running time is poly-logarithmic in the order of G.

Mariano Zelke, Humboldt University Berlin

Weighted Matching in Streaming Graphs

    The Semi-Streaming Model forbids random access to the input and uses a working memory of restricted size. It was proposed by Muthukrishnan in 2003 and is appropriate when tackling massive graphs. For the problem of finding the maximum weighted matching, which is intractable in the Semi-Streaming Model, we will present the best known approximation algorithm.

Kontakt:

Dr. Mihyun Kang 
Postanschrift
Johann von Neumann-Haus
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin


Tel.   : (+49 30) 2093 3830
Fax    : (+49 30) 2093 3191
e-mail : kang@informatik.hu-berlin.de
zuletzt geändert am 20.06.2008 (alkox-www)