טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGoldbraikh Adam
SubjectOnline Disjoint Set Cover without Prior Knowledge
DepartmentDepartment of Applied Mathematics
Supervisor Professor Yuval Emek


Abstract

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).