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

ReLU neural networks of polynomial size for exact maximum flow computation

MATHEMATICAL PROGRAMMING 2025年第1-2期210卷 377-406页

作者： Hertrich, Christoph Sering, Leon Univ libre Bruxelles Dept Math Brussels Belgium Swiss Fed Inst Technol Dept Math Zurich Switzerland

This paper studies the expressive power of artificial neural networks with rectified linear units. In order to study them as a model of real-valued computation, we introduce the concept of Max-Affine Arithmetic Programs and show equivalence between them and neural networks concerning natural complexity measures. We then use this result to show that two fundamental combinatorial optimization problems can be solved with polynomial-size neural networks. First, we show that for any undirected graph with n nodes, there is a neural network (with fixed weights and biases) of size O(n3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n<^>3)$$\end{document} that takes the edge weights as input and computes the value of a minimum spanning tree of the graph. Second, we show that for any directed graph with n nodes and m arcs, there is a neural network of size O(m2n2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(m<^>2n<^>2)$$\end{document} that takes the arc capacities as input and computes a maximum flow. Our results imply that these two problems can be solved with strongly polynomial time algorithms that solely use affine transformations and maxima computations, but no comparison-based branchings.

关键词： Neural network expressivity strongly polynomial algorithms Minimum spanning tree problem Maximum flow problem

来源：评论

学校读者我要写书评

暂无评论

RATIONALITY AND strongly polynomial SOLVABILITY OF EISENBERG-GALE MARKETS WITH TWO AGENTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第3期24卷 1117-1136页

作者： Chakrabarty, Deeparnab Devanur, Nikhil R. Vazirani, Vijay V. Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Microsoft Res Redmond WA USA Georgia Tech Coll Comp Atlanta GA 30332 USA

Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84-106] introduced the class of Eisenberg-Gale (EG) markets. We study the structure of EG(2) markets, the class of EG markets with two agents. We prove that all markets in this class are rational, that is, they have rational equilibrium, and they admit strongly polynomial time algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial linear program (LP). This helps positively resolve the status of two markets left as open problems by Jain and Vazirani: the capacity allocation market in a directed graph with two source-sink pairs and the network coding market in a directed network with two sources. Our algorithms for solving the corresponding nonlinear convex programs are fundamentally different from those obtained by Jain and Vazirani;whereas they use the primal-dual schema, our main tool is binary search powered by the strong LP-duality theorem.

关键词： market equilibrium strongly polynomial algorithms convex programs

来源：评论

学校读者我要写书评

暂无评论

A strongly polynomial Algorithm for Generalized Flow Maximization

引用

MATHEMATICS OF OPERATIONS RESEARCH 2017年第1期42卷 179-211页

作者： Vegh, Laszlo A. London Sch Econ & Polit Sci Dept Math London WC2A 2AE England

A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution and thus can be contracted. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per column in the constraint matrix.

关键词： network flow algorithms generalized flows strongly polynomial algorithms linear programming

来源：评论

学校读者我要写书评

暂无评论

polynomial combinatorial algorithms for skew-bisubmodular function minimization

引用

MATHEMATICAL PROGRAMMING 2018年第1-2期171卷 87-114页

作者： Fujishige, Satoru Tanigawa, Shin-ichi Kyoto Univ Res Inst Math Sci Kyoto Japan Ctr Wiskunde & Informat Amsterdam Netherlands

Huber et al. (SIAM J Comput 43: 1064-1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28: 1828-1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12: 1-9, 2014) also showed a min-max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization.

关键词： Skew-bisubmodular functions Submodular functions Discrete convexity Combinatorial algorithms strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

A strongly polynomial simplex method for the linear fractional assignment problem

引用

OPERATIONS RESEARCH LETTERS 2008年第4期36卷 402-407页

作者： Kabadi, Santosh N. Punnen, Abraham P. Simon Fraser Univ Dept Math Surrey BC V3T 0A3 Canada Univ New Brunswick Fac Business Adm Fredericton NB Canada

In this paper we show that the complexity of the simplex method for the linear fractional assignment problem (LFAP) is strongly polynomial. Although LFAP can be solved in polynomial time using various algorithms such as Newton's method or binary search, no polynomial time bound for the simplex method for LFAP is known. (C) 2007 Elsevier B.V. All rights reserved.

关键词： assignment problem linear fractional programming simplex method complexity strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

strongly polynomial FPTASes for Monotone Dynamic Programs

引用

ALGORITHMICA 2022年第10期84卷 2785-2819页

作者： Alon, Tzvi Halman, Nir Hebrew Univ Jerusalem Jerusalem Israel Bar Ilan Univ Ramat Gan Israel

In this paper we introduce a framework for the automatic generation of strongly polynomial Fully polynomial Time Approximation Schemes (SFPTASes) for monotone dynamic programs. While some ad-hoc SFPTASes for specific problems are already known, this is the first framework yielding such SFPTASes. In addition, it is possible to use our algorithm to get efficient (non strongly polynomial) FPTASes. Our results are derived by improving former (non strongly polynomial) FPTASes which were designed via the method of K-approximation sets and functions. We demonstrate our SFPTAS framework on five application problems, namely, 0/1 Knapsack, counting 0/1 Knapsack, Counting s - t paths, Mobile agent routing and Counting n-tuples, for the last problem we get the fastest SFPTAS known to date. In addition, we use our algorithm to get the fastest (non strongly polynomial) FPTASes for the following other three application problems: Stochastic ordered knapsack, Bi-criteria path problem with maximum survival probability and Minimizing the makespan of deteriorating jobs.

关键词： strongly polynomial algorithms Dynamic programming K-approximation sets and functions

来源：评论

学校读者我要写书评

暂无评论

A strongly polynomial ALGORITHM FOR A CLASS OF MINIMUM-COST FLOW PROBLEMS WITH SEPARABLE CONVEX OBJECTIVES

引用

SIAM JOURNAL ON COMPUTING 2016年第5期45卷 1729-1761页

作者： Vegh, Laszlo A. London Sch Econ Dept Math London WC2A 2AE England

A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective Sigma(ij is an element of Epsilon) C-ij (f(ij)) over feasible flows f, where on every arc ij of the network, C-ij is a convex function. We give a strongly polynomial algorithm for the case when all C-ij's are convex quadratic functions, settling an open problem raised, e.g., by Hochbaum [Math. Oper. Res., 19 (1994), pp. 390-409]. We also give strongly polynomial algorithms for computing market equilibria in Fisher markets with linear utilities and with spending constraint utilities that can be formulated in this framework (see Shmyrev [J. Appl. Ind. Math., 3 (2009), pp. 505-518], Birnbaum, Devanur, and Xiao [Proceedings of the 12th ACM Conference on Electronic Commerce, 2011, pp. 127-136]). For the latter class this resolves an open question raised by Vazirani [Math. Oper. Res., 35 (2010), pp. 458-478]. The running time is O(m(4) log m) for quadratic costs, O(n(4)+n(2)(m+n log n) log n) for Fisher's markets with linear utilities, and O(mn(3) + m(2)(m + n log n) logm) for spending constraint utilities. All these algorithms are presented in a common framework that addresses the general problem setting. Whereas it is impossible to give a strongly polynomial algorithm for the general problem even in an approximate sense (see Hochbaum [Math. Oper. Res., 19 (1994), pp. 390-409]), we show that assuming the existence of certain black-box oracles, one can give an algorithm using a strongly polynomial number of arithmetic operations and oracle calls only. The particular algorithms can be derived by implementing these oracles in the respective settings.

关键词： network flow algorithms convex optimization strongly polynomial algorithms market equilibrium computation

来源：评论

学校读者我要写书评

暂无评论

A strongly polynomial ALGORITHM FOR MINIMUM CONVEX SEPARABLE QUADRATIC COST FLOW PROBLEMS ON 2-TERMINAL SERIES-PARALLEL NETWORKS

引用

MATHEMATICAL PROGRAMMING 1993年第1期59卷 117-132页

作者： TAMIR, A NYU NEW YORKNY 10003

We present strongly polynomial algorithms to find rational and integer flow vectors that minimize a convex separable quadratic cost function on two-terminal series-parallel graphs.

关键词： QUADRATIC COST FLOW PROBLEMS strongly polynomial algorithms SERIES PARALLEL GRAPHS

来源：评论

学校读者我要写书评

暂无评论

ReLU Neural Networks of polynomial Size for Exact Maximum Flow Computation 1

引用

24th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Hertrich, Christoph Sering, Leon London Sch Econ & Polit Sci London England Swiss Fed Inst Technol Zurich Switzerland

ISBN: (数字)9783031327261

ISBN: (纸本)9783031327254;9783031327261

关键词： Neural Network Expressivity strongly polynomial algorithms Minimum Spanning Tree Problem Maximum Flow Problem

来源：评论

学校读者我要写书评

暂无评论

strongly polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives 12

Strongly Polynomial Algorithm for a Class of Minimum-Cost Fl...

引用

44th ACM Annual Symposium on Theory of Computing (STOC)

作者： Vegh, Laszlo A. Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

ISBN: (纸本)9781450312455

A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective E-ij is an element of E C-ij(f(ij)) over feasible flows f, where on every arc ij of the network, C-ij is a convex function. We give a strongly polynomial algorithm for finding an exact optimal solution for a broad class of such problems. The key characteristic of this class is that an optimal solution can be computed exactly provided its support. This includes separable convex quadratic objectives and also certain market equilibria problems: Fisher's market with linear and with spending constraint utilities. We thereby give the first strongly polynomial algorithms for separable quadratic minimum-cost flows and for Fisher's market with spending constraint utilities, settling open questions posed e.g. in [15] and in [35], respectively. The running time is O(m(4) log m) for quadratic costs, O(n(4)+n(2)(m+n log n) log n) for Fisher's markets with linear utilities and O(mn(3)+m(2)(m+ n log n) log m) for spending constraint utilities.

关键词： network flow algorithms convex optimization strongly polynomial algorithms market equilibrium

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：