Thesis topic proposal
Competitive analysis of online and semi-online algorithms


Institute: University of Szeged
computer sciences
PhD School in Computer Science

Thesis supervisor: Csanád Imreh
Location of studies: SZTE
Abbreviation of location of studies: SZTE

Description of the research topic:

In on-line optimization, an algorithm must make its decisions based only on past events without any solid information about future data. Such algorithms are called online algorithms. Since an online algorithm makes its decisions based only on partial information, without knowing the whole instance in advance, we cannot expect it to give the optimal solution that can be produced by an algorithm that has all the necessary information. An algorithm that knows the whole input in advance is called an offline algorithm.

In this research project the plan is to use a worst-case analysis approach called competitive analysis to measure the efficiency of the algorithms. This means that we compare the objective function value of the solution produced by the on-line algorithm with the optimal offline objective function value. With online minimization problems, an online algorithm is called C-competitive if, for each input, the cost of the solution created by the algorithm is at most $C$ times more than the optimal offline cost. The competitive ratio of an algorithm is the smallest C for which the algorithm is C-competitive.

In some applications we have some a priori information on the input in advance, or the algorithm is allowed to postpone some of its decisions or modify some of them after the arrival of the next part of the input. These models are called semi-online, and the algorithms developed for them are also called semi-online. They can be analyzed in the same way as the online algorithms, by performing a competitive analysis. An important subfield of semi-online algorithms is the area of advice complexity. This approach measures how much knowledge (number of bits given by an expert knowing the full input) an online algorithm needs in order to achieve a certain competitive ratio.

Further requirements: 
Research topic for foreign applicants.

Number of students who can be accepted: 1

Deadline for application: 2017-03-31

All rights reserved © 2007, Hungarian Doctoral Council. Doctoral Council registration number at commissioner for data protection: 02003/0001. Program version: 1.2334 ( 2017. I. 15. )