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 ...
详细信息
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) timealgorithms 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)-timealgorithms 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) timealgorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first poly(n, k) timealgorithms, even for approximate computation. Together, these three structures encompass many-if not most-current applications of MOT.
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 observabi...
详细信息
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.
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 sec...
详细信息
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.
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 infe...
详细信息
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 polynomialtime, 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.
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 k...
详细信息
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 pseudopolynomialalgorithms there is no algorithm that solves any non-trivial subclass in polynomialtime. 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 polynomialtime. 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.
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 k...
详细信息
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 pseudopolynomialalgorithms there is no algorithm that solves any non-trivial subclass in polynomialtime. 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 polynomialtime. 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.
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...
详细信息
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.
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 exa...
详细信息
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.
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 func...
详细信息
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.
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...
详细信息
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.
暂无评论