Bejelentkezés
 Fórum
 
 
Témakiírás
 
Competitive analysis of online and semi-online algorithms

TÉMAKIÍRÁS

Intézmény: Szegedi Tudományegyetem
informatikai tudományok
Informatika Doktori Iskola

témavezető: Imreh Csanád
helyszín: SZTE
helyszín rövidítés: SZTE


A kutatási téma leírása:

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.

további elvárások: 
Research topic for foreign applicants.

felvehető hallgatók száma: 1

Jelentkezési határidő: 2017-03-31

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 1.2318 ( 2016. XI. 26. )