Rastislav Královič

Rastislav Královič


Research Focus & Metrics

Academic Career Length

30Years (1997-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 April 2003 in Journal of Discrete Algorithms
Verified
Journal Article
Closed access
PFPaola Flocchini
Paola Flocchini
RKRastislav Královič
Rastislav Královič
PRPeter Ružička
Peter Ružička
ARAlessandro Roncato
Alessandro Roncato
NSNicola Santoro
Nicola Santoro

1 January 2009
Verified
Book Chapter
Closed access
PDF file
HBHans-Joachim Böckenhauer
Hans-Joachim Böckenhauer
DKDennis Komm
Dennis Komm
RKRastislav Královič
Rastislav Královič
RKRichard Královič
Richard Královič
TMTobias Mömke
Tobias Mömke

4 April 2009 in RAIRO - Theoretical Informatics and Applications
Verified
Journal Article
Closed access
PDF file
SDStefan Dobrev
Stefan Dobrev
RKRastislav Královič
Rastislav Královič
DPDana Pardubská
Dana Pardubská
We propose a new way of characterizing the complexity of online problems. Instead of measuring the degradation of the output quality caused by the ignorance of the future we choose to quantify the amount of additional global information needed for an online algorithm to solve the problem optimally. In our model, the algorithm cooperates with an oracle that can see the whole input. We define the advice complexity of the problem to be the minimal number of bits (normalized per input request, and minimized over all algorithm-oracle pairs) communicated by the algorithm to the oracle in order to solve the problem optimally. Hence, the advice complexity measures the amount of problem-relevant information contained in the input. We introduce two modes of communication between the algorithm and the oracle based on whether the oracle offers an advice spontaneously (helper) or on request (answerer). We analyze the Paging and DiffServ problems in terms of advice complexity and deliver upper and lower bounds in both communication modes; in the case of DiffServ problem in helper mode the bounds are tight.

1 January 2010
Verified
Book Chapter
Closed access
PDF file
JHJuraj Hromkovič
Juraj Hromkovič
RKRastislav Královič
Rastislav Královič
RKRichard Královič
Richard Královič

12 January 2006 in Networks
Verified
Journal Article
Closed access
PDF file
SDS. Dobrev
S. Dobrev
PFP. Flocchini
P. Flocchini
RKRastislav Královič
Rastislav Královič
PRP. Ružička
P. Ružička
GPG. Prencipe
G. Prencipe
NSN. Santoro
N. Santoro

1 June 2017 in Information and Computation
Verified
Journal Article
Closed access
HBHans-Joachim Böckenhauer
Hans-Joachim Böckenhauer
DKDennis Komm
Dennis Komm
RKRastislav Královič
Rastislav Královič
RKRichard Královič
Richard Královič
TMTobias Mömke
Tobias Mömke