M.Sc Student | Goldbraikh Adam |
---|---|

Subject | Online Disjoint Set Cover without Prior Knowledge |

Department | Department of Applied Mathematics |

Supervisor | Professor Yuval Emek |

The *disjoint set cover* (DSC)
problem is a fundamental combinatorial optimization problem concerned with
partitioning the (hyper)edges of a hypergraph into (pairwise disjoint) clusters
--- each identified with a unique *color* --- so that the number of colors
that cover all nodes is maximized.

In its *online* version, the
edges arrive one-by-one and should be colored (i.e., assigned to clusters) in
an irrevocable fashion without knowing the future edges.

The quality of online DSC algorithms
is measured by means of their *competitive ratio*, namely, the ratio of
the number of covering colors obtained by an optimal omniscience algorithm to
that of the online algorithm in the worst case.

A hypergraph parameter that plays an important role in this regard is the minimum node degree δ that servers as an upper bound on the number of covering colors and hence, can be used as a benchmark for competitive analysis.

The existing literature on the online DSC problem works under the assumption that the minimum node degree δ (or an approximation thereof) is known to the online algorithm at all times.

The main goal of the research conducted in the course of my master studies is to lift this assumption and design online DSC algorithms that do not hold any prior knowledge of δ.

Our main positive result is the first (randomized) online DSC algorithm that guarantees poly-logarithmic competitive ratio without prior knowledge of δ.

On the negative side, we establish the first lower bound on the competitive ratio of randomized online DSC algorithms (that holds even if the online algorithm does know δ in advance).