Maintaining the Minimal Distance of a Point Set in Poly-logarithmic Time.
Measuring the problem-relevant information in input
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...
Medze efektivnosti paralelných výpočtových systémov
Memory complexity of countable functions
Mince zajímají nejen numismatiky
V článku představíme dva druhy úloh týkajících se platby mincemi, které souvisejí s optimalitou počtu použitých mincí. V případě problému platby (říká se také rozměňování — anglicky change making problem), tj. skládání částky z mincí bez možnosti vracení, jsou úlohy spojené s optimalitou dobře prozkoumané. Analogické úlohy zformulujeme pro směnu, tj. skládání částky z mincí s možností vracení. Zde zůstává naopak řada problémů otevřená.
Minimum common string partition problem: hardness and approximations.
Minimum Dissection of a Rectilinear Polygon with Arbitrary Holes into Rectangles.
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm...
More on the complexity of cover graphs
In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.
Motions of a Short-Linked Robot Arm in a Square.