Zobrazeno 1 - 10
of 50
pro vyhledávání: '"Mihaľák, Matúš"'
Autor:
Mihalak, Matus
We study four problems arising in the area of communication networks. The minimum-weight dominating set problem in unit disk graphs asks, for a given set D of weighted unit disks, to find a minimum-weight subset D' ⊆ D such that the disks D' in
Externí odkaz:
http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.436662
In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a $(2/3)$-approximation for the Maximum Independent Set problem on interval graphs. We show that this is tight, even on unit interval graphs of maxim
Externí odkaz:
http://arxiv.org/abs/2403.10868
Autor:
Martinez, Virginia Aardevol, Chaplick, Steven, Kelk, Steven, Meuwese, Ruben, Mihalak, Matus, Stamoulis, Georgios
There are multiple factors which can cause the phylogenetic inference process to produce two or more conflicting hypotheses of the evolutionary history of a set X of biological entities. That is: phylogenetic trees with the same set of leaf labels X
Externí odkaz:
http://arxiv.org/abs/2309.01110
Let $G$ be an undirected graph. We say that $G$ contains a ladder of length $k$ if the $2 \times (k+1)$ grid graph is an induced subgraph of $G$ that is only connected to the rest of $G$ via its four cornerpoints. We prove that if all the ladders con
Externí odkaz:
http://arxiv.org/abs/2302.10662
In manufacturing, the production is often done on out-of-the-shelf manufacturing lines, whose underlying scheduling heuristics are not known due to the intellectual property. We consider such a setting with a black-box job-shop system and an unknown
Externí odkaz:
http://arxiv.org/abs/2212.07543
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS'18, pages 56:1-56:16, 2018
We consider k mobile agents initially located at distinct nodes of an undirected graph (on n nodes, with edge lengths) that have to deliver a single item from a given source node s to a given target node t. The agents can move along the edges of the
Externí odkaz:
http://arxiv.org/abs/1809.00077
Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The pro
Externí odkaz:
http://arxiv.org/abs/1807.01962
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We consider the classical machine scheduling, where $n$ jobs need to be scheduled on $m$ machines, and where job $j$ scheduled on machine $i$ contributes $p_{i,j}\in \mathbb{R}$ to the load of machine $i$, with the goal of minimizing the makespan, i.
Externí odkaz:
http://arxiv.org/abs/1611.04159