………. DOT's blog ……….

VL “Statistische Mechanik und Optimierung auf zufälligen Strukturen”

In Algorithmen und Zufall, Teaching(DE) on January 27, 2012 at 13:22

Im kommenden Sommersemester werde ich eine Vorlesung zum Thema

Statistische Mechanik und Optimierung auf zufälligen Strukturen

anbieten. Hinter dem Titel verbirgt sich die folgende (normalerweise aus der Praxis stammende) Kritik an der traditionellen Analyse von Optimierungsalgorithmen:

Was schert mich, dass man mit viel Mühe eine Instanz konstruieren kann, bei der mein Algorithmus schlecht funktioniert, wenn man solche Instanzen suchen muss wie die Nadel im Heuhaufen?

In der Vorlesung sollen Ansätze aus der Statistischen Mechanik benutzt werden, um Algorithmen zu konstruieren, die (beweisbar) nur bei “Ausnahmen” schlecht funktionieren.

Statistische Mechanik ist (im Grunde) ein Teilgebiet der Wahrscheinlichkeitstheorie, und zwar netterweise, aufgrund der Ursprünge in der Physik, ein sehr intuitives. Physikkenntnisse brauchen Sie für die Vorlesung aber nicht.

Der Inhalt der Vorlesung zerfällt auf natürliche Art in drei Zeitabschnitte.

Einführung: einige einfache Algorithmen auf zufälligen Strukturen
Statistische Mechanik für Nicht-Physiker
Aus der Statistischen Mechanik abgeleitete Algorithmen

Voraussetzungen

Einführung in die Wahrscheinlichkeitstheorie und Statistik
Kombinatorische Optimierung

Weitere organisatorische und inhaltliche Informationen

werde ich als Kommentare zu diesem Blogpost schreiben (s.u. bei Responses). Interessenten und Teilnehmer sind gleichfalls eingeladen, sich in den Kommentaren mit Fragen und Kritik zu Wort zu melden!!

Parallel zur Vorlesung soll ein ausfürliches Skript entstehen.

Comment »

VL Kombinatorische Optimierung WS 2011/12

In Komb-Opt, Teaching(DE) on October 12, 2011 at 13:01

Liebe Übungsteilnehmer,

Dieser Post ist der Vorlesung “Kombinatorische Optimierung” (WS 2011/12) gewidmet.

In den Responses (unten klicken) finden sich

die Übungsblätter
(hoffentlich) Ihre Fragen, Kommentare und Diskussionen zur VL und den Übungsblättern (gerne anonym)
Ankündigungen zur VL bzw zum Übungsbetrieb

Das jeweils neue Übungsblatt wird im Laufe des Donnerstags hochgeladen, und ein Link als Kommentar gepostet.

Übungen
Nur noch mal ganz kurz:

Donnerstag	9:15-10:45	G02 / 209
	13:30-15:00	G14 / 125

Scheinkriterien

Für fortgeschrittene VLs wie der Kombinatorischen Optimierung gibt es keine Zettelkorrekturen mehr. Daher fällt das übliche Kriterium “50% der Übungszettelpunkte” für den Schein weg. Um Sie zu motivieren, trotzdem die Übungsaufgaben zu lösen (und damit Ihre Chancen zu verbessern, die Klausur zu bestehen), folgen wir seit einiger Zeit dem folgenden kleveren Ansatz (mit Varianten):

Einziges Scheinkriterium ist Bestehen der Klausur mit mind. 50% der Punkte
Jeder VL-Teilnehmer wird zur Klausur zugelassen
In den Übungen werden die Übungsaufgaben zur Klausur von frewilligen Übungsteilnehmern vorgerechnet
Für das Vorrechnen können Bonuspunkte zur Klausur gewonnen werden, und zwar 0%, 5% oder 10% pro Aufgabe, abhängig von der Qualität der dargestellten Lösung (10% gibt’s nur bei korrekter Lösung und perfekter Präsentation)
Melden sich mehrere Freiwillige zum Vorrechnen der gleichen Aufgabe, so wird aus denjenigen mit geringster Punktzahl einer zufällig ausgewält
Maximal 40% der Klausurpunkte können vor der Klausur erlangt werden

Außerdem soll es ein Programmierprojekt geben, mit dem Sie Klausurprozente schnorren können. Details dazu gibt es im Lauf der VL. Punkt (6) oben gilt inklusive der Projektpunkte.

Zum Schluss
den Hinweis auf meine Sprechzeiten und Kontaktdaten.

Viel Spaß bei der VL!

Comment »

Open questions about nonnegative rank and related concepts

In NnegRk, Research on August 16, 2011 at 08:52

This posts summarizes some my favorite open problems about the nonnegative rank of matrices and related concepts like extension complexity of polytopes (see this post.)

Some notation & terminology:

$\mbox{frk}_S$	factorization rank over the semiring S
$\mbox{ndCC}(A)$	nondeterministic communication complexity of the support of A
$\mbox{fool}(A)$	fooling set bound

Theoretical questions

Cohen & Rothblum (1993) asked: If ${A}$ is rational, is its factorization rank over ${\mathbf{Q}_+}$ equal to the factorization rank over ${\mathbf{R}_+}$ ? More generally: If ${A}$ has entries in a sub-semiring ${S}$ of a sub-semiring ${R}$ of the nonnegative reals, how large can the gap be between ${\mbox{frk}_S(A)}$ and ${\mbox{frk}_R(A)}$ ? (Beasley & Laffey 2009)
Given any sub-semiring ${S}$ of ${\mathbf{R}_+}$ and ${n\ge 6}$ , is there a matrix ${A \in \mathbf{M}_{n\times n}(S)}$ such that ${\mbox{rk} A = 3}$ and ${\mbox{frk}_S(A) = n}$ ? (Beasley & Laffey 2009) This is open even for ${S=\mathbf{R}_+}$ . Cf. Specific-Question #1.
If ${A}$ is a symmetric ${n\times n}$ nonnegative matrix with real rank ${k}$ , and if ${A}$ has exactly one negative eigenvalue, must ${A}$ have a nonnegative factorization ${A = XY}$ where ${X}$ is ${n\times q}$ with ${q}$ bounded as a function of ${k}$ ? (Beasley & Laffey 2009)
What is the smallest $\alpha$ such that $\mbox{rk}_+(A) \le \mbox{rk}(A)^\alpha$ for all 01-matrices $A$ ? This corresponds to Lovász and Saks log-rank conjecture (with $\alpha = \infty$ if that is false). Proving lower bounds for $\alpha$ corresponds to proving lower bounds for the nonnegative rank.
What is the largest separation between the logarithm of the nonnegative rank and the deterministic communication complexity for Boolean functions? The gap cannot be more than quadratic, but the best known example has a smaller gap. A related question asks for the largest separation between the nonnegative rank and the biclique covering number for 01-matrices.
It is known that $\mbox{fool}(A) \le (\mbox{rk} A)^2$ . (Dietzfelbinger Hromkovic Juraj Schnitger (1996)), and there are examples where ${\mbox{fool}(A) \ge (\mbox{rk} A)^{\log_3 4}}$ . Which of these two bounds can be improved? (Dietzfelbinger, Hromkovic, Juraj, Schnitger 1996)

Questions about specific families of matrices

A ${d}$ -dimensional, Euclidean distance Matrix of size ${n}$ is defined by points ${x_1,\dots,x_n}$ in ${d}$ -dimensional Euclidean space. Its entries are ${\bigl( \lVert x_k - x_\ell \rVert )_{k,\ell}}$ . Do “generic”/“random” Euclidean distance Matrices have full nonnegative rank? (Gillis & Glineur 2011; Lin & Chu 2010). A proof of this for ${d=1}$ by Lin & Chu 2010 is fatally flawed. More spcifically: Do some linear Euclidean distance Matrices have the propery asked for in Theory-Question #2? (Beasley & Laffey 2009) (Not all of them do (Gillis & Glineur 2011).)

The rank bound and the ndCC bound are both trivial for these matrices. Upper bounds for special cases have been improved. (Gillis & Glineur 2011)
Does a random (with a suitable distribution) ${(m\times n)}$ rank- ${k}$ matrix have full nonnegative rank? A weaker question asked by J. Garcke, M. Klimm, H.-C. Kreusler, and A. Uschmajew is: Has the set of matrices with nonnegative rank- ${k}$ has positive Lebesgue measure within the ${(m\times n)}$ rank- ${k}$ matrices? If ${A}$ is randomly drawn from the ${(m\times n)}$ -matrices with nonnegative rank ${k}$ , is ${\mbox{rk} A = k}$ with probability one / positive probability? (Dong, Lin, Chu)
For some of these questions, erroneous proofs can be found on the internet. In particular, a proof by Dong, Lin, and Chu is incorrect. The rank bound and the ndCC bound are both trivial for these matrices.
Is the extension complexity of the Matching Polytope of an ${n}$ -vertex graph polynomial in ${n}$ ?
An infamous, several decades old question in Combinatorial Optimization asks, whether there exist an extended formulation for the matching problem whose coding size is polynomial in the number of vertices of the graph. A slightly weaker question asks whether there exist an extended formulation whose number of inequalities is bounded by a polynomial in the number of vertices of the graph. The best known lower bound is the trivial rank bound ${\Omega(n^2)}$ . The ndCC bound is ${O(n^4).}$ The known upper bounds are ${O(c^n)}$ , for values of ${c\in \left]1,2\right]}$ which have been improved several times in the last three decades.
Is the extension complexity of the Spanning Tree polytope ${\Omega(n^3)}$ ?.
Michele Goemans asked this question at the Cargese Workshop on Combinatorial Optimization 2010, which was dedicated to extended formulations. The best known lower bound is the trivial rank bound. It is unknown whether the ndCC bound improves on the rank bound. The known upper bound is ${O(n^3)}$ , with improvements for certain types of graphs.
What is the extension complexity of the Stable Set polytope of a perfect graph?
The question goes back to Yannakakis (1991), and was recently repeated by Michele Goemans (MIT) at the Cargese Workshop on Combinatorial Optimization 2010, which was dedicated to extended formulations.
Is the extension complexity of the Completion Time polytope ${O(n\log n)}$ ? (Goemans 2011 & Cargese)
If true, this would extend work by Goemans (2011). The best known lower bound is the trivial rank bound. The upper bound is ${O(n^2)}$ , which has been proved in a couple of ways in the last 20 years.
Is the extension complexity of an ${n}$ -vertex convex polygon with vertices in general position ${\Omega(n)}$ ? (Fiorini, Rothvoss, Tiwary) The rank bound is 2, the ndCC bound is ${\Omega(\log n)}$ . Some regular convex polygons have extension complexity ${\Theta(\log n)}$ . The best known lower bound for algebraically independent vertices is ${\Omega(\sqrt n)}$ .