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

Computing the Degree of Determinants via Discrete convex Optimization on Euclidean Builuiags

SIAM JOURNAl ON APPlIED AlGEBRA AND GEOMETRY 2019年第3期3卷 523-557页

作者： Hirai, Hiroshi Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Tokyo 1138656 Japan

In this paper, we consider the computation of the degree of the Dieudonne determinant of a linear symbolic matrix A = A(0) + A(1)x(1) + ...+ A(m)x(m), where each A is an n x n polynomial matrix over K[t] and x(1), x(2), ..., x m are pairwise "noncommutative" variables. This quantity is regarded as a weighted generalization of the noncommutative rank (nc-rank) of a linear symbolic matrix, and its computation is shown to be a generalization of several basic combinatorial optimization problems, such as weighted bipartite matching and weighted linear matroid intersection problems. Based on the work on nc-rank by Fortin and Reutenauer [Sem. lothar. Combin., 52 (2004), B52f] and Ivanyos, Qiao, and Subrahmanyam [Comput. Complex., 27 (2018), pp. 561-593], we develop a framework to compute the degree of the Dieudonne determinant of a linear symbolic matrix. We show that the deg-det computation reduces to a discrete convex optimization problem on the Euclidean building for Sl(K(t)(n)). To deal with this optimization problem, we introduce a class of discrete convex functions on the building. This class is a natural generalization of l-convex functions in discrete convex analysis (DCA). We develop a DCA-oriented algorithm (steepest descent algorithm) to compute the degree of determinants. Our algorithm works with matrix computation on K and uses a subroutine to compute a certificate vector subspace for the nc-rank, where the number of calls of the subroutine is sharply estimated. Our algorithm enhances some classical combinatorial optimization algorithms with new insights, and it is also understood as a variant of the combinatorial relaxation algorithm, which was developed earlier by Murota for computing the degree of the (ordinary) determinant.

关键词： noncommutative rank Dieudonne determinant skew field discrete convex analysis mixed matrix combinatorial relaxation algorithm submodular function l-convex function Euclidean building uniform modular lattice

来源：评论

学校读者我要写书评

暂无评论

l-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem

引用

DISCRETE OPTIMIZATION 2015年 18卷 1-37页

作者： Hirai, Hiroshi Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Tokyo 1138656 Japan

In this paper, we develop a theory of new classes of discrete convex functions, called l-extendable functions and alternating l-convex functions, defined on the product of trees. We establish basic properties for optimization: a local-to-global optimality criterion, the steepest descend algorithm by successive k-submodular function minimizations, the persistency property, and the proximity theorem. Our theory is motivated by minimum cost free multiflow problem. To this problem, Goldberg and Karzanov gave two combinatorial weakly polynomial time algorithms based on capacity and cost scalings, without explicit running time. As an application of our theory, we present a new simple polynomial proximity scaling algorithm to solve minimum cost free multiflow problem in Omicron(n log(nAC)MF(kn, km)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum of edge-costs, C is the total sum of edge-capacities, and MF(n', m') denotes the time complexity to find a maximum flow in a network of n' nodes and m' edges. Our algorithm is designed to solve, in the same time complexity, a more general class of multiflow problems, minimum cost node-demand multiflow problem, and is the first combinatorial polynomial time algorithm to this class of problems. We also give an application to network design problem. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Discrete convex analysis l-convex function k-submodular function Multicommodity flows

来源：评论

学校读者我要写书评

暂无评论

Algorithms in discrete convex analysis

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2000年第3期E83D卷 344-352页

作者： Murota, K Kyoto Univ Math Sci Res Inst Kyoto 6068502 Japan

This is a survey of algorithmic results in the theory of "discrete convex analysis" for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, the Fenchel min-max duality, and separation theorems. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms.

关键词： discrete convex analysis matroid l-convex function M-convex function

来源：评论

学校读者我要写书评

暂无评论

A survey of fundamental operations on discrete convex functions of various kinds

引用

OPTIMIZATION METHODS & SOFTWARE 2021年第2-3期36卷 472-518页

作者： Murota, Kazuo Tokyo Metropolitan Univ Dept Econ & Business Adm Tokyo Japan

Discrete convex functions are used in many areas, including operations research, discrete-event systems, game theory, and economics. The objective of this paper is to offer a survey on fundamental operations for various kinds of discrete convex functions in discrete convex analysis such as integrally convex functions, l-convex functions, M-convex functions, and multimodular functions.

关键词： Discrete convex analysis integrally convex function l-convex function M-convex function multimodular function submodular function valuated matroid

来源：评论

学校读者我要写书评

暂无评论

Note on multimodularity and l-convexity

引用

MATHEMATICS OF OPERATIONS RESEARCH 2005年第3期30卷 658-661页

作者： Murota, K Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan

Multimodular functions and l-convex functions have been investigated almost independently, but they are, in fact, equivalent objects that can be related through a unimodular coordinate transformation. Some facts known for l-convex functions can be translated to new results for multimodular functions, and vice versa. In particular, the local optimality condition for global optimality found in the literature of multimodular functions should be rectified, and a discrete separation theorem holds for multimodular functions.

关键词： discrete convex function multimodular function l-convex function local optimality

来源：评论

学校读者我要写书评

暂无评论

Abstract cyclical monotonicity and Monge solutions for the general Monge-Kantorovich problem

引用

SET-VAlUED ANAlYSIS 1999年第1期7卷 7-32页

作者： levin, V Russian Acad Sci Cent Econ & Math Inst Moscow 117418 Russia

Abstract cyclical monotonicity is studied for a multivalued operator F : X --> l, where l subset of or equal to R-X. A criterion for F to be l-cyclically monotone is obtained and connections with the notions of l-convex function and of its l-subdifferentials are established. Applications are given to the general Monge-Kantorovich problem with fixed marginals. In particular, we show that in some cases the optimal measure is unique and generated by a unique (up to the a.e. equivalence) optimal solution (measure preserving map) for the corresponding Monge problem.

关键词： l-cyclical monotonicity l-convex function l-subdifferential multifunction Q(0) general Monge-Kantorovich problem measure preserving map

来源：评论

学校读者我要写书评

暂无评论

On steepest descent algorithms for discrete convex functions

引用

SIAM JOURNAl ON OPTIMIZATION 2004年第3期14卷 699-707页

作者： Murota, K Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan JST PRESTO Tokyo 1138656 Japan

This paper investigates the complexity of steepest descent algorithms for two classes of discrete convex functions: M-convex functions and l-convex functions. Simple tie-breaking rules yield complexity bounds that are polynomials in the dimension of the variables and the size of the effective domain. Combining the present results with a standard scaling approach leads to an efficient algorithm for l-convex function minimization.

关键词： discrete optimization discrete convex function steepest descent algorithm M-convex function l-convex function

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：