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

Values for level structures with polynomial-time algorithms, relevant coalition functions, and general considerations

引用

DISCRETE APPLIED MATHEMATICS 2022年 309卷 85-109页

作者： Besner, Manfred Univ Appl Sci Dept Geomat Comp Sci & Math HFT Stuttgart Schellingstr 24 D-70174 Stuttgart Germany

Exponential runtimes of algorithms for values for games with transferable utility like the Shapley value are one of the biggest obstacles in the practical application of otherwise axiomatically convincing solution concepts of cooperative game theory. We investigate to what extent the hierarchical structure of a level structure improves runtimes compared to an unstructured player set. Representatively, we examine the Shapley levels value, the nested Shapley levels value, and, as a new value for level structures, the nested Owen levels value. For these values, we provide polynomial-time algorithms (under normal conditions) which are exact and therefore not approximation algorithms. Moreover, we introduce relevant coalition functions where all coalitions that are not relevant for the payoff calculation have a Harsanyi dividend of zero. Our results shed new light on the computation of values of the Harsanyi set as the Shapley value and many values from extensions of this set. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Cooperative game polynomial-time algorithm Level structure (Nested) Shapley/Owen (levels) value Harsanyi dividends

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for Phylogenetic Inference Problems Involving Duplication and Reticulation

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2020年第1期17卷 14-26页

作者： van Iersel, Leo Janssen, Remie Jones, Mark Murakami, Yukihiro Zeh, Norbert Delft Univ Technol Delft Inst Appl Math Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands Dalhousie Univ Fac Comp Sci 6050 Univ Ave Halifax NS B3H 1W5 Canada

A common problem in phylogenetics is to try to infer a species phylogeny from gene trees. We consider different variants of this problem. The first variant, called Unrestricted Minimal Episodes Inference, aims at inferring a species tree based on a model with speciation and duplication where duplications are clustered in duplication episodes. The goal is to minimize the number of such episodes. The second variant, Parental Hybridization, aims at inferring a species network based on a model with speciation and reticulation. The goal is to minimize the number of reticulation events. It is a variant of the well-studied Hybridization Number problem with a more generous view on which gene trees are consistent with a given species network. We show that these seemingly different problems are in fact closely related and can, surprisingly, both be solved in polynomial time, using a structure we call "beaded trees". However, we also show that methods based on these problems have to be used with care because the optimal species phylogenies always have a restricted form. To mitigate this problem, we introduce a new variant of Unrestricted Minimal Episodes Inference that minimizes the duplication episode depth. We prove that this new variant of the problem can also be solved in polynomial time.

关键词： Phylogenetics duplication MINIMUM EPISODES problem HYBRIDIZATION NUMBER problem gene trees inference polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

An entire space polynomial-time algorithm for linear programming

引用

JOURNAL OF GLOBAL OPTIMIZATION 2014年第1期58卷 109-135页

作者： Tian, Da Gang Shanghai Univ Sci & Technol Sch Business Shanghai 201800 Peoples R China

We propose an entire space polynomial-time algorithm for linear programming. First, we give a class of penalty functions on entire space for linear programming by which the dual of a linear program of standard form can be converted into an unconstrained optimization problem. The relevant properties on the unconstrained optimization problem such as the duality, the boundedness of the solution and the path-following lemma, etc, are proved. Second, a self-concordant function on entire space which can be used as penalty for linear programming is constructed. For this specific function, more results are obtained. In particular, we show that, by taking a parameter large enough, the optimal solution for the unconstrained optimization problem is located in the increasing interval of the self-concordant function, which ensures the feasibility of solutions. Then by means of the self-concordant penalty function on entire space, a path-following algorithm on entire space for linear programming is presented. The number ofNewton steps of the algorithm is no more than O(nL log(nL/epsilon)), and moreover, in short step, it is no more than O(root n log(nL/epsilon)).

关键词： polynomial-time algorithm Linear programming Entire space Self-concordance Penalty function

来源：评论

学校读者我要写书评

暂无评论

The complexity of growing a graph ☆

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 147卷

作者： Mertzios, George Michail, Othon Skretas, George Spirakis, Paul G. Theofilatos, Michail Univ Durham Dept Comp Sci Durham England Univ Liverpool Dept Comp Sci Liverpool England Univ Potsdam Hasso Plattner Inst Potsdam Germany

We study a new algorithmic process of graph growth which starts from a single initial vertex and operates in discrete time-steps, called slots. In every slot, the graph grows via two operations (i) vertex generation and (ii) edge activation. The process completes at the last slot where a (possibly empty) subset of the edges of the graph are removed. Removed edges are called excess edges. The main problem investigated in this paper is: Given a target graph G, design an algorithm that outputs a process that grows G, called a growth schedule. Additionally, we aim to minimize the total number of slots k and of excess edges P used by the process. We provide both positive and negative results, with our main focus being either schedules with sub-linear number of slots or with no excess edges. (c) 2024 Published by Elsevier Inc.

关键词： Dynamic graph Temporal graph Cop-win graph Graph process polynomial-time algorithm Lower bound NP-complete Hardness result

来源：评论

学校读者我要写书评

暂无评论

Adapting stable matchings to forced and forbidden pairs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 147卷

作者： Boehmer, Niclas Heeger, Klaus TU Berlin Ernst Reuter Pl 7 D-10587 Berlin Germany Univ Potsdam Hasso Plattner Inst Potsdam Germany Ben Gurion Univ Negev Beer Sheva Israel

We introduce the problem of adapting a stable matching to forced and forbidden pairs. Given a stable matching M-1, a set Q of forced pairs, and a set P of forbidden pairs, we want to find a stable matching that includes all pairs from Q, no pair from P, and is as close as possible to M-1. We study this problem in four classic stable matching settings: Stable Roommates (with Ties) and Stable Marriage (with Ties). Our main contribution is a polynomial-time algorithm, based on the theory of rotations, for adapting Stable Roommates matchings to forced pairs. In contrast, we show that the same problem for forbidden pairs is NP-hard. However, our polynomial-time algorithm for forced pairs can be extended to a fixed-parameter tractable algorithm with respect to the number of forbidden pairs. Moreover, we study the setting where preferences contain ties: Some of our algorithmic results can be extended while other problems become intractable. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Stable Marriage Stable Roommates Forced and forbidden pairs Incremental algorithms Rotations NP-hardness polynomial-time algorithm W[1]-hardness FPT

来源：评论

学校读者我要写书评

暂无评论

Characterization and algorithm for bivariate multi-unit assignment valuations

引用

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS 2024年第1期41卷 359-380页

作者： Otsuka, Takafumi Shioura, Akiyoshi Tokyo Inst Technol Dept Ind Engn & Econ Tokyo 1528550 Japan

A multi-unit assignment valuation is a function represented by a weighted bipartite graph. In this paper, we provide a characterization of such a function in terms of maximizer sets of perturbed functions. We then present an algorithm that checks whether a given bivariate function is a multi-unit assignment valuation, and if the answer is "yes," computes a weighted bipartite graph representing the function.

关键词： Assignment valuation Bipartite graph Discrete concave function polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The complexity of transitively orienting temporal graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 150卷

作者： Mertzios, George B. Molter, Hendrik Renken, Malte Spirakis, Paul G. Zschoche, Philipp Univ Durham Dept Comp Sci Durham England Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Tech Univ Berlin Algorithm & Computat Complex Berlin Germany Univ Liverpool Dept Comp Sci Liverpool England

In a temporal network with discrete time-labels on its edges, information can only "flow" along sequences of edges with non-decreasing (resp. increasing) time-labels. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. By naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation, and we systematically investigate its algorithmic behavior. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a temporal graph G is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether G is strictly transitively orientable. Additionally we introduce further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Temporal graph Transitive orientation Transitive closure polynomial-time algorithm NP-hardness Satisfiability

来源：评论

学校读者我要写书评

暂无评论

The Minimum Centroid Branch Spanning Tree Problem

引用

Journal of the Operations Research Society of China 2024年第2期12卷 528-539页

作者： Hao Lin Cheng He School of Science Henan University of TechnologyZhengzhou450001HenanChina

For a spanning tree T of graph G,the centroid of T is a vertex v for which the largest component of T-v has as few vertices as *** number of vertices of this component is called the centroid branch weight of *** minimum centroid branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is *** application to design of communication networks,the loads of all branches leading from the switch center should be as balanced as *** this paper,we prove that the problem is strongly NP-hard even for bipartite ***,the problem is shown to be polynomially solvable for split graphs,and exact formulae for special graph familis,say Kn_(1),n_(2),...,n_(k)and P_(m)×P_(n),are presented.

关键词： Spanning tree optimization Centroid branch-NP-hardness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The Implication Problem for Functional Dependencies and Variants of Marginal Distribution Equivalences

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2024年第4期25卷 1-23页

作者： Hirvonen, Minna Univ Helsinki Helsinki Finland

We study functional dependencies together with two different probabilistic dependency notions: unary marginal identity and unary marginal distribution equivalence. A unary marginal identity states that two variables x and y are identically distributed. A unary marginal distribution equivalence states that the multiset consisting of the marginal probabilities of all the values for variable x is the same as the corresponding multiset for y . We present a sound and complete axiomatization for the class of these dependencies and show that it has Armstrong relations. The axiomatization is infinite, but we show that there can be no finite axiomatization. The implication problem for the subclass that contains only functional dependencies and unary marginal identities can be simulated with functional dependencies and unary inclusion atoms, and therefore the problem is in polynomial-time. This complexity bound also holds in the case of the full class, which we show by constructing a polynomial-time algorithm.

关键词： Armstrong relations complete axiomatization functional dependency inclusion dependency marginal distribution equivalence polynomial-time algorithm probabilistic team semantics

来源：评论

学校读者我要写书评

暂无评论

SOLVING THE MAXIMUM POPULAR MATCHING PROBLEM WITH MATROID CONSTRAINTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第3期38卷 2226-2242页

作者： Csaji, Gergely Kiraly, Tamas Yokoi, Yu Eotvos Lorand Univ Dept Operat Res Budapest Hungary HUN REN Ctr Econ & Reg Studies Mech Design Res Grp Budapest Hungary Eotvos Lorand Univ HUN REN ELTE Egervary Res Grp Dept Operat Res Budapest Hungary Tokyo Inst Technol Sch Comp Dept Math & Comp Sci Tokyo Japan

We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Kamiyama [Theoret. Comput. Sci., 809 (2020), pp. 265--276] and solved in the special case where matroids are base orderable. Utilizing a newly shown matroid exchange property, we show that the problem is tractable for arbitrary matroids. We further investigate a different notion of popularity, where the agents vote with respect to lexicographic preferences, and show that both existence and verification problems become coNP-hard even in the b-matching case.

关键词： matroid popular matching polynomial-time algorithm stable matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：