Journal: Journal of Computer and System Sciences

Abbreviation

J. comput. syst. sci

Publisher

Elsevier

Journal Volumes

ISSN

0022-0000
1090-2724

Description

Filters

Reset filters

Search Results

Publications 1 - 10 of 19
  • On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
    Item type: Journal Article
    Ďuriš, Pavol; Hromkovič, Juraj; Inoue, Katsushi (2004)
    Journal of Computer and System Sciences
  • Robust optimization in the presence of uncertainty: A generic approach
    Item type: Journal Article
    Buhmann, Joachim M.; Gronskiy, Alexey; Mihalák, Matúš; et al. (2018)
    Journal of Computer and System Sciences
    We propose a novel approach for optimization under uncertainty. Our approach does not assume any particular noise model behind the measurements, and only requires two typical instances. We first propose a measure of similarity of instances (with respect to a given objective). Based on this measure, we then choose a solution randomly among all solutions that are near-optimum for both instances. The exact notion of near-optimum is intertwined with the proposed similarity measure. Our similarity measure also allows us to derive formal statements about the expected quality of the computed solution. Furthermore, we apply our approach to various optimization problems.
  • On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
    Item type: Journal Article
    Pietrzak, Krzysztof (2003)
    Journal of Computer and System Sciences
  • k-Majority digraphs and the hardness of voting with a constant number of voters
    Item type: Journal Article
    Bachmeier, Georg; Brandt, Felix; Geist, Christian; et al. (2019)
    Journal of Computer and System Sciences
  • Call control with k rejections
    Item type: Journal Article
    Anand, R. Sai; Erlebach, Thomas; Hall, Alexander; et al. (2003)
    Journal of Computer and System Sciences
  • Greedy routing and the algorithmic small-world phenomenon
    Item type: Journal Article
    Bringmann, Karl; Keusch, Ralph; Lengler, Johannes; et al. (2022)
    Journal of Computer and System Sciences
    The algorithmic small-world phenomenon, empirically established by Milgram in the 60 s [1], was theoretically explained by Kleinberg in 2000 [2]. However, from today's perspective his model has several severe shortcomings that limit the applicability to real-world networks. In order to give a more convincing explanation, we study decentralized greedy routing in a random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings. We prove that greedy routing succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length Θ(loglogn), with stretch 1+o(1). Moreover, natural local patching methods ensure success probability 1, while maintaining the same stretch. These results also address the question whether there are efficient local routing protocols for the internet graph. Despite promising experimental studies the question remained unsolved theoretically. We give for the first time a rigorous, affirmative answer for a thoroughly validated model of the internet graph. © 2021 Elsevier Inc.
  • Infinite vs. finite size-bounded randomized computations
    Item type: Journal Article
    Královič, Richard (2014)
    Journal of Computer and System Sciences
  • On the Power of Safe Locking
    Item type: Journal Article
    Lausen, Georg; Soisalon-Soininen, Eljas; Widmayer, Peter (1990)
    Journal of Computer and System Sciences
  • On the advice complexity of the k-server problem
    Item type: Journal Article
    Böckenhauer, Hans-Joachim; Komm, Dennis; Královič, Rastislav; et al. (2017)
    Journal of Computer and System Sciences
  • What one has to know when attacking P vs NP
    Item type: Journal Article
    Hromkovič, Juraj; Rossmanith, Peter (2020)
    Journal of Computer and System Sciences
Publications 1 - 10 of 19