检索结果-内蒙古大学图书馆

Robust two-dose vaccination schemes and the directed b-matching problem

DISCRETE APPLIED MATHEMATICS 2024年 356卷 369-392页

作者： Segschneider, Jenny Koster, Arie M. C. A. Rhein Westfal TH Aachen Res Area Discrete Optimizat Aachen Germany

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/).

关键词： Directed matching Computational complexity graph and network algorithms Robust optimization Optimal vaccination scheduling

来源：评论

学校读者我要写书评

暂无评论

Minimum cut bases in undirected networks

引用

DISCRETE APPLIED MATHEMATICS 2010年第4期158卷 277-290页

作者： Bunke, Florentine Hamacher, Horst W. Maffioli, Francesco Schwahn, Anne M. Tech Univ Kaiserlautern Dept Math D-67653 Kaiserslautern Germany Politecn Milan Dept Elect & Informat I-20133 Milan Italy

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.

关键词： Cut basis problem graph and network algorithms Integer programming

来源：评论

学校读者我要写书评

暂无评论

An Edge-Fencing Strategy for Optimizing SSSP Computations on Large-Scale graphs 21

An Edge-Fencing Strategy for Optimizing SSSP Computations on...

引用

50th International Conference on Parallel Processing (ICPP)

作者： Yu, Huashan Wang, Xiaolin Luo, Yingwei Peking Univ Dept Comp Sci & Technol Beijing Peoples R China Peng Cheng Lab Shenzhen Peoples R China

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.

关键词： graph and network algorithms scalability parallel performance

来源：评论

学校读者我要写书评

暂无评论

Infrastructure leasing problems

引用

12th International Integer Programming and Combinatorial Optimization Conference

作者： Anthony, Barbara M. Gupta, Anupam Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA USA

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.

关键词： Approximation algorithms graph and network algorithms Randomized algorithms Stochastic combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Optimal Vaccination Strategies for Multiple Dose Vaccinations 7th

Optimal Vaccination Strategies for Multiple Dose Vaccination...

引用

7th International Symposium on Combinatorial Optimization (ISCO)

作者： Segschneider, Jenny Koster, Arie M. C. A. Rhein Westfal TH Aachen Res Area Discrete Optimizat Aachen Germany

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.

关键词： Computational complexity graph and network algorithms

来源：评论

学校读者我要写书评

暂无评论

A 4/3-approximation algorithm for minimum 3-edge-connectivity

引用

10th International Workshop on algorithms and Data Structures

作者： Gubbala, Prabhakar Raghavachari, Balaji Microsoft Corp Redmond WA 98052 USA Univ Texas Dallas Comp Sci Dept Richardson TX 75083 USA

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

关键词： approximation algorithms graph and network algorithms connectivity combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Semantic Query Transformations for Increased Parallelization in Distributed Knowledge graph Query Processing 19

Semantic Query Transformations for Increased Parallelization...

引用

International Conference for High Performance Computing, networking, Storage and Analysis (SC)

作者： Kim, Hyeongsik Bhattacharyya, Abhisha Anyanwu, Kemafor Robert Bosch LLC Sunnyvale CA 94085 USA North Carolina State Univ Raleigh NC USA

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.

关键词： graph and network algorithms improved models algorithms performance or scalability of specific applications and respective software cloud workflow data resource management including dynamic resource provisioning data analytics and frameworks supporting data analytics Scalable storage metadata namespaces data management

来源：评论

学校读者我要写书评

暂无评论

There are spanning spiders in dense graphs (and we know how to find them)

There are spanning spiders in dense graphs (and we know how ...

引用

30th International Colloquium on Automata, Languages and Programming (ICALP 2003)

作者： Gargano, L Hammar, M Univ Salerno Dipartimento Informat & Applicaz I-84081 Baronissi Italy

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.

关键词： graph theory graph and network algorithms

来源：评论

学校读者我要写书评

暂无评论

Relaxed update and partition network games

引用

FUNDAMENTA INFORMATICAE 2002年第4期49卷 301-312页

作者： Bodlaender, HL Dinneen, MJ Khoussainov, B Univ Utrecht Inst Comp & Informat Sci NL-3508 TB Utrecht Netherlands Univ Auckland Dept Comp Sci Auckland 1 New Zealand

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.

关键词： graph and network algorithms complexity infinite graph games McNaughton games

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：