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

polynomial-time algorithms for multimarginal optimal transport problems with structure

MATHEMATICAL PROGRAMMING 2023年第1-2期199卷 1107-1178页

作者： Altschuler, Jason M. Boix-Adsera, Enric MIT Lab Informat & Decis Syst LIDS 77 Massachusetts Ave Cambridge MA 02139 USA

Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n. This paper develops a general theory about what "structure" makes MOT solvable in poly(n, k) time. We develop a unified algorithmic framework for solving MOT in poly(n, k) time by characterizing the structure that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in poly(n, k) time. Second, our framework makes it much simpler to develop poly(n, k) time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle-which is much more amenable to standard algorithmic techniques. We illustrate this ease-ofuse by developing poly(n, k)-time algorithms for three general classes of MOT cost structures: (1) graphical structure;(2) set-optimization structure;and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has poly(n, k) runtime;moreover, we provide the first poly(n, k) time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first poly(n, k) time algorithms, even for approximate computation. Together, these three structures encompass many-if not most-current applications of MOT.

关键词： Multimarginal optimal transport polynomial-time algorithms Implicit linear programming Structured linear programs

来源：评论

学校读者我要写书评

暂无评论

Minimal Control Nodes for Strong Structural Observability of Discrete-time Iterative Systems: Explicit Formulas and polynomial-time algorithms

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2024年第4期69卷 2158-2173页

作者： Zhu, Shiyong Lu, Jianquan Ho, Daniel W. C. Cao, Jinde Southeast Univ Sch Math Dept Syst Sci Nanjing 210096 Peoples R China City Univ HongKong Dept Elect Engn Hong Kong Peoples R China City Univ Hong Kong Dept Math Hong Kong Peoples R China Southeast Univ Sch Math Nanjing 210096 Peoples R China Southeast Univ Frontiers Sci Ctr Mobile Informat Commun & Secur Nanjing 210096 Peoples R China

In this article, we initiate an important class of vertex-marked directed graphs, referred to as the strong structurally observable graphs (SSOGs), to be the fundamental structural architectures ensuring the observability of several prevalent types of discrete-time iteration systems. This article also answers the minimal control node problem of SSOGs by carrying out two explicit formulas and the corresponding polynomial-time algorithms. Primitively, by exploring the strong structural observability of Boolean networks, an underlying class of SSOGs is proposed as an extended counterpart of network structures of observable conjunctive Boolean networks, while we call for particular attention to network structures instead of node dynamics. With such a class of SSOGs, we justify that a general class of discrete-time iterative systems can also be well addressed. In our formulation, the robustness against the uncertainties in nodal dynamics is achieved by merely exploiting the information on network structures. Two minimal synthesis strategies are, respectively, established to render a directed graph strongly structurally observable in a polynomial amount of time via placing a minimal number of sensors or controlling the nodes. Notably, apart from explicitly calculating the minimal set of control nodes, the structural insights are also leveraged to account for the close relations between the observability of considered iteration systems and observed-path-compatible paths and cycles in the network structures. For certain special yet worthy cases, the SSOGs are specialized in the strong structural observability of finite-field networks and derive the minimum pinned node theorem of Boolean networks with a biological case study as an efficient demonstration.

关键词： Observability Sensors Heuristic algorithms Directed graphs Galois fields Control systems Finite element analysis Boolean networks discrete-time systems explicit formulas minimum control nodes polynomial-time algorithms strong structural observability

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for single resource stochastic capacity expansion models with lost sales

引用

INFOR 2021年第4期59卷 572-591页

作者： Taghavi, Majid Huang, Kai Golmohammadi, Amirmohsen St Marys Univ Sobey Sch Business 923 Robie St Halifax NS B3H 3C3 Canada McMaster Univ DeGroote Sch Business Hamilton ON Canada Laurentian Univ Fac Management Sudbury ON Canada

In this paper, we consider multi-period single resource stochastic capacity expansion problems with lost sales. We study two models. The first model does not consider fixed-charge for capacity purchases, while the second one incorporates fixed-charges. We use multi-stage stochastic integer programs to present both models and show how adding the fixed-charge cost changes the structure of the mathematical models. For both models, we study their structures and design polynomial-time algorithms to solve them. We present computational results to show the performance of the designed algorithms.

关键词： Capacity expansion multi-stage stochastic integer programming dynamic programming lost sales single resource polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for Phylogenetic Inference Problems 5th

Polynomial-Time Algorithms for Phylogenetic Inference Proble...

引用

5th International Conference on algorithms for Computational Biology (AlCoB)

作者： 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

ISBN: (纸本)9783319919386;9783319919379

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 of 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 of speciation and reticulation. The goal is to minimize the number of reticulation events. It is a variant of the wellstudied 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 some restricted form. We discuss several possibilities to overcome this problem.

关键词： Phylogenetic inference problems polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for Energy Games with Special Weight Structures

Polynomial-Time Algorithms for Energy Games with Special Wei...

引用

20th Annual European Symposium on algorithms (ESA)

作者： Chatterjee, Krishnendu Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon IST Austria Klosterneuburg Austria Univ Vienna Fac Comp Sci Vienna Austria Nanyang Technol Univ Singapore 639798 Singapore

ISBN: (纸本)9783642330896

Energy games belong to a class of turn-based two-player infinite-duration games played on a weighted directed graph. It is one of the rare and intriguing combinatorial problems that lie in NPa (c) co-NP, but are not known to be in P. The existence of polynomial-time algorithms has been a major open problem for decades and apart from pseudopolynomial algorithms there is no algorithm that solves any non-trivial subclass in polynomial time. In this paper, we give several results based on the weight structures of the graph. First, we identify a notion of penalty and present a polynomial-time algorithm when the penalty is large. Our algorithm is the first polynomial-time algorithm on a large class of weighted graphs. It includes several worst-case instances on which previous algorithms, such as value iteration and random facet algorithms, require at least sub-exponential time. Our main technique is developing the first non-trivial approximation algorithm and showing how to convert it to an exact algorithm. Moreover, we show that in a practical case in verification where weights are clustered around a constant number of values, the energy game problem can be solved in polynomial time. We also show that the problem is still as hard as in general when the clique-width is bounded or the graph is strongly ergodic, suggesting that restricting the graph structure does not necessarily help.

关键词： Graph algorithms polynomial-time algorithms Turn-based infinite duration games Energy games Mean-payoff games

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for Energy Games with Special Weight Structures

引用

ALGORITHMICA 2014年第3期70卷 457-492页

关键词： Graph algorithms polynomial-time algorithms Turn-based infinite duration games Energy games Mean-payoff games

来源：评论

学校读者我要写书评

暂无评论

On the geometric red-blue set cover problem

引用

THEORETICAL COMPUTER SCIENCE 2025年 1033卷

作者： Madireddy, Raghunath Reddy Nandy, Subhas C. Pandit, Supantha Birla Inst Technol & Sci Pilani Hyderabad Campus Pilani India Indian Stat Inst Kolkata India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

Using various geometric objects, we study variations of the geometric Red-Blue Set Cover (RBSC) problem in & Ropf;2. Here, given two sets R and B of points, called red and blue points, respectively, and a set O of objects, the objective is to compute a subset O ' C O of objects such that O ' covers all the blue points in B and covers the minimum number of red points in R. We show that the RBSC problem with intervals on the real line is polynomial-time solvable. In & Ropf;2, the problem admits a polynomial-time algorithm for a particular case of axis-parallel lines when no two lines intersect at a red point. However, if the objects are horizontal lines and vertical segments, the problem becomes NP-hard. It remains NP-hard for axis-parallel unit length segments distributed arbitrarily in the plane. The problem is NP-hard for the axis-parallel rectangles even when (i) each rectangle in O is anchored at one of the given two parallel lines, and (ii) a horizontal line intersects all the rectangles in O. We show a variation of RBSC, called Special Red Blue Set Cover (SPECIAL-RBSC), to be APXhard. Next, we use this result to show APX-hardness of the following geometric variations of RBSC problem in & Ropf;2 where the objects are (i) axis-parallel rectangles containing the origin, (ii) axis-parallel strips, (iii) axis-parallel rectangles that are intersecting exactly zero or four times, (iv) axis-parallel line segments, and (v) downward shadows of line segments, by providing the encoding of these problems as the Special Red Blue Set Cover problem. These APX-hardness results are in the same line of work by Chan and Grant (2014), who provided the APX-hardness results for the geometric set cover problem for the above classes of objects.

关键词： Red-blue set cover Special red-blue set cover Anchored rectangles Segments polynomial-time algorithms APX-hard NP-hard

来源：评论

学校读者我要写书评

暂无评论

Critical (P5, dart)-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2025年 366卷 44-52页

作者： Xia, Wen Jooken, Jorik Goedgebeur, Jan Huang, Shenwei Nankai Univ Coll Comp Sci Tianjin 300071 Peoples R China Nankai Univ Tianjin Key Lab Network & Data Secur Technol Tianjin 300071 Peoples R China Katholieke Univ Leuven Dept Comp Sci Campus Kulak Kortrijk B-8500 Kortrijk Belgium Univ Ghent Dept Appl Math Comp Sci & Stat B-9000 Ghent Belgium Nankai Univ Sch Math Sci Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China

Given two graphs H 1 and H 2 , a graph is (H1, H 2 )-free if it contains no induced subgraph isomorphic to H 1 nor H 2 . A dart is the graph obtained from a diamond by adding a new vertex and making it adjacent to exactly one vertex with degree 3 in the diamond. In this paper, we show that there are finitely many k-vertex-critical (P5, dart)-free graphs for k >= 1. To prove these results, we use induction on k and perform a careful structural analysis via the Strong Perfect Graph Theorem combined with the pigeonhole principle based on the properties of vertex-critical graphs. Moreover, fork E { 5 , 6, 7} we characterize all k-vertex-critical (P5, dart)-free graphs using a computer generation algorithm. Our results imply the existence of a polynomial-time certifying algorithm to decide the k-colorability of (P5, dart)-free graphs fork >= 1 where the certificate is either a k-coloring or a (k+ 1)-vertex-critical induced subgraph. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Graph coloring k-critical graphs Strong perfect graph theorem polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Increasing the Maximum Capacity Path in a Network and Its Application for Improving the Connection Between Two Routers

引用

Tsinghua Science and Technology 2024年第3期29卷 753-765页

作者： Adrian M.Deaconu Javad Tayyebi Department of Mathematics and Computer Science Transilvania University of BrasovBrasov 500036Romania Department of Industrial Engineering Birjand University of TechnologyBirjand 000097Iran

Abstract:This paper addresses the problem of improving the optimal value of the Maximum Capacity Path(MCP)through expansion in a flexible network,and minimizing the involved *** only condition applied to the cost functions is to be non-decreasing *** is a non-restrictive condition,reflecting the reality in practice,and is considered for the first time in the ***,the total cost of expansion is a combination of max-type cost(e.g.,for supervision)and sum-type cost(*** building infrastructures,price of materials,price of labor,etc.).For this purpose,two types of strategies are combined:(l)increasing the capacity of the existing arcs,and(l)adding potential new *** different problems are introduced and *** the problems have immediate applications in Internet routing *** first one is to extend the network,so that the capacity of an McP in the modified network becomes equal to a prescribed value,therefore the cost of modifications is minimized.A strongly polynomial-time algorithm is deduced to solve this *** second problem is a network expansion under a budget constraint,so that the capacity of an McP is maximized.A weakly polynomial-time algorithm is presented to deal with *** the special case when all the costs are linear,a Meggido's parametric search technique is used to develop an algorithm for solving the problem in strongly polynomial *** new approach has a time complexity of O(n^(4)),which is better than the time complexity of O(n4 log(n)of the previously known method from literature.

关键词： Maximum Capacity Path(MCP) network expansion Internet routing polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

The Complexity of Finding Fair Many-to-One Matchings

引用

ACM TRANSACTIONS ON algorithms 2024年第2期20卷 1-37页

作者： Boehmer, Niclas Koana, Tomohiro Tech Univ Berlin Str 17 Juni 135 D-10623 Berlin Germany

We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side is matched to exactly one vertex and each vertex from the "right" side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices. Assuming that each vertex from the left side has one color modeling its "attribute", we study two fairness criteria. For instance, in one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is, for instance, relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively. We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. We establish the correctness of our integer programs, based on Frank's separation theorem [Frank, Discrete Math. 1982]. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side.

关键词： Graph theory polynomial-time algorithms NP-hardness FPT ILP color coding submodular and supermodular functions algorithmic fairness

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：