Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

• People
  • Personnel
  • Guests
  • Alumni
• Reports
  • Current Report
  • Report for 2023
  • Report for 2022
  • Previous Reports
• Research
  • Grants
  • Dissertations
  • Master/Bachelor Theses
  • Current Publications
  • Previous Publications
• Mittagsseminar
• Courses
• Thesis Topics
• Events
  • Workshops
    • Current
    • Previous
  • Social
    • SOLA
    • GREBGE
• 

Towards The Peak - Problem Section

The Product Algorithm Works

presented by Günter Rothe

A slight modification of the product algorithm for finding the sink in a unique sink orientation will, for all orientations, find either a sink or a certificate. Let $\phi$ be an orientation of the d-dimensional cube $\cal C$. Choose k directions $i_1,{\ldots} ,i_k$ of $\cal C$. This partitions $\cal C$ into 2^k subcubes of dimension d-k, each subcube corresponds to a vertex in the k-dimensional cube ${\cal C}^{(k)}=2^{\{i_1,{\ldots} ,i_k\}}$. Denote by ${\cal C}_v$ the subcube corresponding to $v\in{\cal C}^{(k)}$. We will solve the d-dimensional problem by applying a k-dimensional algorithm to ${\cal C}^{(k)}$ with a (d-k)-dimensional algorithm as oracle.

More precisely, for a vertex $v\in{\cal C}^{(k)}$ we will apply a (d-k)-dimensional algorithm to the corresponding subcube ${\cal C}_v$. Either this algorithm finds a certificate or a sink in ${\cal C}_v$. In the first case, since a certificate in a subcube is a global certificate, the product algorithm can stop and return this certificate. In the case it found a sink w, this vertex w defines the orientations in v: An edge from v in direction i_j is outgoing iff the edge from w in direction i_j is outgoing with respect to $\phi$.

Now the k-dimensional algorithm either finds a sink or a certificate in ${\cal C}^{(k)}$. If it finds a sink, this has to be a global sink and can be returned. If it finds a certificate, the sinks of the corresponding subcubes are global certificates and it can return them.

The product algorithm gives a recursive formula of

$$D(d)\leq D(k)D(d-k)$$

for all $0\leq k\leq d$. Using D(3)=5 we get an upper bound

D(d)=O(1.71^d).

Imprint Disclaimer Copyright