In light of the recent pandemic and the shortage of vaccinations during their rollout, questions arose regarding the best strategy to achieve immunity throughout the population by adjusting the time gap between the tw...
详细信息
In light of the recent pandemic and the shortage of vaccinations during their rollout, questions arose regarding the best strategy to achieve immunity throughout the population by adjusting the time gap between the two necessary vaccination doses. This strategy has already been studied from different angles by various researches. However, the deliveries of vaccination doses also proved to be highly uncertain, with manufacturers not being able to deliver the promised amount of vaccines on time. In this paper, we study the robust version of this problem and its generalization to matchings on arbitrary graphs. By exploring the problem, we show that it is weakly NPhard for a constant number of scenarios and strongly NP-hard else. Further, we propose a pseudo-polynomial algorithm for the weakly NP-hard subproblem with a constant number of scenarios and time between both doses. Finally, we perform computational experiments to better understand the behavior of the problem. (c) 2024 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://***/licenses/by-nc/4.0/).
Due to the COVID-19 pandemic and the shortage of vaccinations during its roll-out, the question regarding the best strategy to achieve immunity in the population by adjusting the time between the two necessary vaccina...
详细信息
ISBN:
(纸本)9783031185298;9783031185304
Due to the COVID-19 pandemic and the shortage of vaccinations during its roll-out, the question regarding the best strategy to achieve immunity in the population by adjusting the time between the two necessary vaccination doses was intensively discussed. This strategy has already been studied from various angles by various researches. However, the combinatorial optimization problem and its complexity has not been the focus of attention. In this paper, we study the complexity of different versions of this problem by first proposing a simple approach using a matching algorithm. Then, we extend the approach by adding constraints and multiple manufacturers. Finally, we discuss a variation of the problem where three vaccinations are necessary, including the so-called "booster". This problem turns out to be NP-hard.
The Single-Source Shortest Path (SSSP) problem is to compute the shortest distances in a weighted graph from a source vertex to every other vertex. This paper focuses on parallel efficiency and scalability of SSSP com...
详细信息
ISBN:
(纸本)9781450390682
The Single-Source Shortest Path (SSSP) problem is to compute the shortest distances in a weighted graph from a source vertex to every other vertex. This paper focuses on parallel efficiency and scalability of SSSP computations on large-scale graphs. We propose an edge-fencing strategy to customize a SSSP algorithm's schedule for every SSSP computation, and devise a path-centric SSSP algorithm with this strategy. This strategy aims at reducing both the relaxed edges and relaxations repeated on each edge. It exploits a few fence values to select the relaxed edges and schedule edge relaxations according to lengths of the created paths. The path-centric algorithm works on a hierarchical graph model, and exploits the edge-fencing strategy to schedule edge relaxations in parallel settings. The hierarchical graph model quantifies the length distribution of shortest paths in large-scale graphs, provides appropriate fence values for every SSSP computation. The algorithm was evaluated on a wide range of synthetic graphs and real-world graphs. The experimental results suggest that our algorithm is efficient and scalable for graphs with skewed degree distributions, and its performance is relatively insensitive to the hierarchical graph model's accuracy.
Ontologies have become an increasingly popular semantic layer for integrating multiple heterogeneous datasets. However, significant challenges remain with supporting efficient and scalable processing of queries with d...
详细信息
ISBN:
(数字)9781450362290
ISBN:
(纸本)9781450362290
Ontologies have become an increasingly popular semantic layer for integrating multiple heterogeneous datasets. However, significant challenges remain with supporting efficient and scalable processing of queries with data linked with ontologies (ontological queries). Ontological query processing queries requires explicitly defined query patterns be expanded to capture implicit ones, based on available ontology inference axioms. However, in practice such as in the biomedical domain, the complexity of the ontological axioms results in significantly large query expansions which present day query processing infrastructure cannot support. In particular, it remains unclear how to effectively parallelize such queries. In this paper, we propose data and query transformations that enable inter-operator parallelism of ontological queries on Hadoop platforms. Our transformation techniques exploit ontological axioms, second order data types and operator rewritings to eliminate expensive query substructures for increased parallelizability. Comprehensive experiments conducted on benchmark datasets show up to 25X performance improvement over existing approaches.
Given an undirected, connected network G = (V, E) with weights oil the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisi...
详细信息
Given an undirected, connected network G = (V, E) with weights oil the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as another graph theoretic problem closely related to it, namely, the cycle basis problem. We consider two versions of the problem: the unconstrained and the fundamental cut basis problem. For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem, and is thus solvable in strongly polynomial time. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each from a spanning tree T, is shown to be NP-hard. In this proof, we also show that a tree which induces the minimum fundamental cycle basis is also an optimal solution for the minimum fundamental cut basis problem in unweighted graphs. We present heuristics, integer programming formulations and summarize first experiences with numerical tests. (C) 2009 Elsevier B.V. All rights reserved.
Consider the following Steiner Tree leasing problem. Given a graph G = (V, E) with root r, and a sequence of terminal sets D-t subset of V for each day t is an element of [T]. A feasible solution to the problem is a s...
详细信息
ISBN:
(纸本)9783540727910
Consider the following Steiner Tree leasing problem. Given a graph G = (V, E) with root r, and a sequence of terminal sets D-t subset of V for each day t is an element of [T]. A feasible solution to the problem is a set of edges E-t for each t connecting D-t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we lease edges for say, { a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.
The minimum cardinality 3-edge-connected spanning sub-graph problem is considered. An approximation algorithm with a performance ratio of 4/3 approximate to 1.33 is presented. This improves the previous best ratio of ...
详细信息
ISBN:
(纸本)9783540739487
The minimum cardinality 3-edge-connected spanning sub-graph problem is considered. An approximation algorithm with a performance ratio of 4/3 approximate to 1.33 is presented. This improves the previous best ratio of 3/2 for the problem. The algorithm also works on multigraphs and guarantees the same approximation ratio.
A spanning spider for a graph G is a spanning tree T of G with at most one vertex having degree three or more in T. In this paper we give density criteria for the existence of spanning spiders in graphs. We constructi...
详细信息
ISBN:
(纸本)3540404937
A spanning spider for a graph G is a spanning tree T of G with at most one vertex having degree three or more in T. In this paper we give density criteria for the existence of spanning spiders in graphs. We constructively prove the following result: Given a graph G with n vertices, if the degree sum of any independent triple of vertices is at least n - 1, then there exists a spanning spider in G. We also study the case of bipartite graphs and give density conditions for the existence of a spanning spider in a bipartite graph. All our proofs are constructive and imply the existence of polynomial time algorithms to construct the spanning spiders. The interest in the existence of spanning spiders originally arises in the realm of multicasting in optical networks. However, the graph theoretical problems discussed here are interesting in their own right.
In this paper, we study the complexity of deciding which player has a winning strategy in certain types of McNaughton games. These graph games can be used as models for computational problems and processes of infinite...
详细信息
In this paper, we study the complexity of deciding which player has a winning strategy in certain types of McNaughton games. These graph games can be used as models for computational problems and processes of infinite duration. We consider the cases (1) where the first player wins when vertices in a specified set are visited infinitely often and vertices in another specified set are visited finitely often, (2) where the first player wins when exactly those vertices in one of a number of specified disjoint sets are visited infinitely often, and (3) a generalization of these first two cases, We give polynomial time algorithms to determine which player has a winning strategy in each of the games considered.
暂无评论