Titlebook: Adventures Between Lower Bounds and Higher Altitudes; Essays Dedicated to Hans-Joachim Böckenhauer,Dennis Komm,Walter Unger Book 2018 Spri

丧失

Grasping

Small Complexity Gaps for Comparison-Based Sortingchieve the first . term, so our focus is on the (negative) constant factor of the linear term. In their WADS2017 paper, Iwama and Teruyama obtained a new upper bound for this constant, which improves the existing gap by some 25%. However, since its main purpose is to have a closed formula for analys

duplicate

Determinism and Nondeterminism in Finite Automata with Advicecognized by . with polynomial advice. We also give examples of languages that cannot be recognized by . with polynomial advice. Finally, we show that increasing advice helps for ., and for any advice of size . we show that there is a language that can be recognized by a . with advice .(.), but canno

ALTER

Stability of Reapproximation Algorithms for the ,-Metric Traveling Salesman (Path) Problemty. Here, if one edge weight is increased, and ., . denotes the relaxation factor of the original and the modified graph, respectively, then we show how to obtain an approximation of ., which improves over existing solutions as soon as ..

期满

Fully Online Matching with Advice on General Bipartite Graphs and Pathswer bounds on the amount of advice that is necessary for computing an optimal solution for paths. We complement these results by bounding the sufficient amount of advice for computing sub-optimal matchings. We furthermore prove that a single bit of advice does not help to improve over deterministic

irradicable

仪式

Small Complexity Gaps for Comparison-Based Sortingforms for the quantity but can obtain an exact average for the number of comparisons up to . efficiently. The major finding is that inserting one or two elements to an already sorted sequence, which is the fundamental strategy of (1,2)Insertion, is quite powerful; we conjecture that more complicated

Compass

gustation

hypnogram

0302-9743 ithms, computer science education, and many other topics within the fields of algorithmics and complexity theory. Moreover, the volume contains a prologue and an epilogue of laudatios from several collaborators, colleagues, and friends..978-3-319-98354-7978-3-319-98355-4Series ISSN 0302-9743 Series E-ISSN 1611-3349