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

polynomial-time algorithms for Multivariate Linear Problems with Finite-Order Weights: Average Case Setting

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2009年第1期9卷 105-132页

作者： Wasilkowski, G. W. Wozniakowski, H. Univ Kentucky Dept Comp Sci Lexington KY 40506 USA Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Warsaw Inst Appl Math PL-02097 Warsaw Poland

We study multivariate linear problems in the average case setting with respect to a zero-mean Gaussian measure whose covariance kernel has a finite-order weights structure. This means that the measure is concentrated on a Banach space of d-variate functions that are sums of functions of at most q* variables and the influence of each such term depends on a given weight. Here q* is fixed whereas d varies and can be arbitrarily large. For arbitrary finite-order weights, based on Smolyak's algorithm, we construct polynomial-time algorithms that use standard information. That is, algorithms that solve the d-variate problem to within e using of order epsilon(-p)d(q)* function values modulo a power of ln epsilon(-1). Here p is the exponent which measures the difficulty of the univariate (d = 1) problem, and the power of ln epsilon(-1) is independent of d. We also present a necessary and sufficient condition on finite-order weights for which we obtain strongly polynomial-time algorithms, i.e., when the number of function values is independent of d and polynomial in epsilon(-1). The exponent of epsilon(-1) may be, however, larger than p. We illustrate the results by two multivariate problems: integration and function approximation. For the univariate case we assume the r-folded Wiener measure. Then p = 1/(r + 1) for integration and p = 1/(r + 1/2) for approximation.

关键词： Tractability Multivariate linear problems polynomial-time algorithms Finite-order weights Small effective dimension Average case setting

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for multivariate linear problems with finite-order weights: Worst case setting

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2005年第4期5卷 451-491页

作者： Wasilkowski, GW Wozniakowski-, H Univ Kentucky Dept Comp Sci Lexington KY 40506 USA Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Warsaw Inst Appl Math PL-02097 Warsaw Poland

We consider approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces with finite-order weights. This means we consider functions of d variables that can be represented as sums of functions of at most q* variables. Here, q* is fixed (and presumably small) and d may be arbitrarily large. For the univariate problem, d = 1, we assume we know algorithms A(1,epsilon) that use O(epsilon(-p)) function or linear functional evaluations to achieve an error epsilon in the worst case setting. Based on these algorithms A(1,epsilon), we provide a construction of polynomial-time algorithms A(d,epsilon) for the general d-variate problem with the number of evaluations bounded roughly by epsilon(-p)d(q*) to achieve an error epsilon in the worst case setting.

关键词： multivariate linear problems tractability polynomial-time algorithms finite-order weights small effective dimension

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 decomposition algorithms for support vector machines

引用

MACHINE LEARNING 2003年第1期51卷 51-71页

作者： Hush, D Scovel, C Los Alamos Natl Lab Los Alamos NM 87545 USA

This paper studies the convergence properties of a general class of decomposition algorithms for support vector machines (SVMs). We provide a model algorithm for decomposition, and prove necessary and sufficient conditions for stepwise improvement of this algorithm. We introduce a simple "rate certifying" condition and prove a polynomial-time bound on the rate of convergence of the model algorithm when it satisfies this condition. Although it is not clear that existing SVM algorithms satisfy this condition, we provide a version of the model algorithm that does. For this algorithm we show that when the slack multiplier C satisfies root1/2 less than or equal to Cless than or equal to mL, where m is the number of samples and L is a matrix norm, then it takes no more than 4LC(2)m(4)/epsilon iterations to drive the criterion to within epsilon of its optimum.

关键词： support vector machines polynomial-time algorithms decomposition algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：