Zobrazeno 1 - 10
of 40
pro vyhledávání: '"Richard Královič"'
Publikováno v:
International Journal of Foundations of Computer Science. 34:145-162
We consider two-tape automata where one tape contains the input word [Formula: see text] and the other an advice string [Formula: see text]. Such an automaton recognizes a language [Formula: see text] if there is an advice function for which every wo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::352f3ad52d10c859bb91d93f74e82121
https://doi.org/10.1142/s0129054122440063
https://doi.org/10.1142/s0129054122440063
Publikováno v:
Algorithmica, 84 (5)
We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8c4669c17d58bf701cd1ab87b78e7992
https://hdl.handle.net/20.500.11850/530894
https://hdl.handle.net/20.500.11850/530894
Publikováno v:
Developments in Language Theory ISBN: 9783030815073
DLT
DLT
We consider two-tape automata where one tape contains the input word w, and the other contains an advice string \(\alpha (|w|)\) for some function \(\alpha :\mathbb {N}\rightarrow \varSigma ^*\). Such an automaton recognizes a language L if there is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::daedb19b432479898bb087b55072a211
https://doi.org/10.1007/978-3-030-81508-0_13
https://doi.org/10.1007/978-3-030-81508-0_13
Autor:
Richard Královič, Sacha Krug, Tobias Mömke, Stefan Dobrev, Rastislav Královič, Dennis Komm, Jeff Edmonds
Publikováno v:
Theoretical Computer Science, 689
We study the advice complexity of an online version of the set cover problem. The goal is to quantify the information that online algorithms for this problem need to be supplied with to compute high-quality solutions and to overcome the drawback of n
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::64b271e5d4f10f6980745dd8c1447f4d
https://doi.org/10.1016/j.tcs.2017.05.029
https://doi.org/10.1016/j.tcs.2017.05.029
Publikováno v:
Information and Computation. 254:59-83
We investigate to what extent the solution quality of online algorithms can be improved when supplying them with information about the input. To this end, we refine the recently introduced notion of advice complexity where the algorithm has access to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b789ee398508aaa8c1e8b3bdcd42c4b8
https://doi.org/10.1016/j.ic.2017.03.001
https://doi.org/10.1016/j.ic.2017.03.001
Autor:
Walter Unger, Xavier Muñoz, Richard Královič, Juraj Hromkovič, Elisabet Burjons, Rastislav Královič
Publikováno v:
International Journal of Foundations of Computer Science, 29 (4)
Recercat. Dipósit de la Recerca de Catalunya
instname
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
instname
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Electronic version of an article published as Online graph coloring against a randomized adversary. "International journal of foundations of computer science", 1 Juny 2018, vol. 29, núm. 4, p. 551-569. DOI:10.1142/S0129054118410058 © 2018 copyright
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::15cf17bf70affe87fb5b38b35ae82a50
https://hdl.handle.net/20.500.11850/274991
https://hdl.handle.net/20.500.11850/274991
Publikováno v:
Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications ISBN: 9783319125671
Adventures Between Lower Bounds and Higher Altitudes
Adventures Between Lower Bounds and Higher Altitudes
We consider the model of finite automata with advice introduced by Kucuk et al. We show that there are languages, in particular the language of palindromes, that cannot be recognized by \(\text {DFA}\) regardless of the size of advice. Also, we show
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a5fbe4013720c9e038d1aab96df3a6c6
https://doi.org/10.1007/978-3-319-98355-4_1
https://doi.org/10.1007/978-3-319-98355-4_1
Publikováno v:
Theory of Computing Systems. 56:197-219
We study the advice complexity of the online version of the Maximum Independent Set problem, restricted to the sparse, and bipartite graphs, respectively. We show that for sparse graphs, constant-sized advice is sufficient to obtain a constant compet
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::60d1d8257642360b7ededa2fcbbbde28
https://doi.org/10.1007/s00224-014-9592-2
https://doi.org/10.1007/s00224-014-9592-2
Autor:
Richard Královič
Publikováno v:
Journal of Computer and System Sciences, 80 (4)
Journal of Computer and System Sciences, 80 (4)
ISSN:0022-0000
ISSN:1090-2724
ISSN:0022-0000
ISSN:1090-2724
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::074648f8f66c147cf53f03eb67b6ea55
https://doi.org/10.1016/j.jcss.2013.11.004
https://doi.org/10.1016/j.jcss.2013.11.004