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

Cone superadditivity of discrete convex functions

MATHEMATICAL PROGRAMMING 2012年第1-2期135卷 25-44页

作者： Kobayashi, Yusuke Murota, Kazuo Weismantel, Robert Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Tokyo 1138656 Japan ETH Dept Math IFOR CH-8092 Zurich Switzerland

A function f is said to be cone superadditive if there exists a partition of R (n) into a family of polyhedral convex cones such that f(z + x) + f(z + y) a parts per thousand currency sign f(z) + f(z + x + y) holds whenever x and y belong to the same cone in the family. This concept is useful in nonlinear integer programming in that, if the objective function is cone superadditive, the global minimality can be characterized by local optimality criterion involving Hilbert bases. This paper shows cone superadditivity of L-convex and M-convex functions with respect to conic partitions that are independent of particular functions. L-convex and M-convex functions in discrete variables (integer vectors) as well as in continuous variables (real vectors) are considered.

关键词： discrete convex function Superadditivity Integer programming Optimality criterion Hilbert bases

来源：评论

学校读者我要写书评

暂无评论

Exact bounds for steepest descent algorithms of L-convex function minimization

引用

OPERATIONS RESEARCH LETTERS 2014年第5期42卷 361-366页

作者： Murota, Kazuo Shioura, Akiyoshi Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

We analyze minimization algorithms for L-q-convex functions in discrete convex analysis and establish exact bounds for the number of iterations required by the steepest descent algorithm and its variants. (C) 2014 Els... 详细信息

关键词： discrete convex function Analysis of algorithm discrete optimization Steepest descent algorithm

来源：评论

学校读者我要写书评

暂无评论

M-convex function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System

引用

MATHEMATICS OF OPERATIONS RESEARCH 2022年第2期47卷 1566-1611页

作者： Shioura, Akiyoshi Tokyo Inst Technol Dept Ind Engn & Econ Tokyo 1528550 Japan

In this paper, we consider a problem of minimizing an M-convex function under an L1-distance constraint (MML1);the constraint is given by an upper bound for L1-distance between a feasible solution and a given "center." This is motivated by a nonlinear integer programming problem for reallocation of dock capacity in a bike-sharing system discussed by Freund et al. (2017). The main aim of this paper is to better understand the combinatorial structure of the dock reallocation problem through the connection with M-convexity and show its polynomial-time solvability using this connection. For this, we first show that the dock reallocation problem and its generalizations can be reformulated in the form of (MML1). We then present a pseudo-polynomial-time algorithm for (MML1) based on the steepest descent approach. We also propose two polynomial-time algorithms for (MML1) by replacing the L1-distance constraint with a simple linear constraint. Finally, we apply the results for (MML1) to the dock reallocation problem to obtain a pseudo-polynomial-time steepest descent algorithm and also polynomial-time algorithms for this problem. For this purpose, we develop a polynomial-time algorithm for a relaxation of the dock reallocation problem by using a proximity-scaling approach, which is of interest in its own right.

关键词： discrete convex function discrete convex analysis resource allocation problem steepest descent algorithm proximity-scaling algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A capacity scaling algorithm for M-convex submodular flow

引用

MATHEMATICAL PROGRAMMING 2005年第1期103卷 181-202页

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

This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.

关键词： discrete optimization discrete convex function submodular flow algorithm

来源：评论

学校读者我要写书评

暂无评论

Shortest bibranchings and valuated matroid intersection

引用

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS 2012年第3期29卷 561-573页

作者： Takazawa, Kenjiro Kyoto Univ Math Sci Res Inst Kyoto 6068502 Japan

For a digraph D = (V, A) and a partition (S, T) of V, an arc set B subset of A is called an S-T bibranching if each vertex in T is reachable from S and each vertex in S reaches T in the subgraph (V, B). Bibranchings commonly generalize bipartite edge covers and arborescences. A totally dual integral linear system determining the S-T bibranching polytope is provided by Schrijver, and the shortest S-T bibranching problem, whose objective is to find an S-T bibranching of minimum total arc weight, can be solved in polynomial time by the ellipsoid method or a faster combinatorial algorithm due to Keijsper and Pendavingh. The valuated matroid intersection problem, introduced by Murota, is a weighted generalization of the independent matching problem, including the independent assignment problem and the weighted matroid intersection problem. The valuated matroid intersection problem can be solved efficiently with polynomially many value oracles by extending classical combinatorial algorithms for the weighted matroid intersection problem. In this paper, we show that the shortest S-T bibranching problem is polynomially reducible to the valuated matroid intersection problem. This reduction suggests one answer to why the shortest S-T bibranching problem is tractable, and implies new combinatorial algorithms for the shortest S-T bibranching problem based on the valuated matroid intersection algorithm, where a value oracle corresponds to computing a minimum-weight arborescence.

关键词： Shortest bibranching Arborescence Valuated matroidintersection discrete convex function

来源：评论

学校读者我要写书评

暂无评论

Concave cocirculations in a triangular grid

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2005年第1-3期400卷 67-89页

作者： Karzanov, AV Russian Acad Sci Inst Syst Anal Moscow 117312 Russia

Let G be a planar digraph embedded in the plane such that each bounded face contains three edges and forms an equilateral triangle, and let the union R of these faces be a convex polygon. We consider the polyhedral cone R(G) formed by the real-valued functions sigma on the set of boundary edges of G with the following property: there exists a concave function c on R which is affinely linear within each bounded face and satisfies c(v) - c(u) = sigma(e) for each boundary edge e = (u, v). Knutson, Tao and Woodward obtained a result on honeycombs which implies that if the polygon R is a triangle, then the cone R(G) is described by linear inequalities of Horn's type with respect to so-called puzzles, along with obvious linear constraints. The purpose of this paper is to give an alternative proof of that result, working in terms of discrete concave functions, rather than honeycombs. Our proof is based on a linear programming approach and a nonstandard flow model. Moreover, the result is extended to an arbitrary convex polygon R as above. (c) 2004 Elsevier Inc. All rights reserved.

关键词： triangular lattice discrete convex function cocirculation planar graph flow

来源：评论

学校读者我要写书评

暂无评论

New algorithms for convex cost tension problem with application to computer vision

引用

discrete OPTIMIZATION 2009年第4期6卷 378-393页

作者： Kolmogorov, Vladimir Shioura, Akiyoshi Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Univ Coll London Martlesham Heath IP5 7RE England

Motivated by various applications to computer vision, we consider the convex cost tension problem, which is the dual of the convex cost flow problem. In this paper, we first propose a primal algorithm for computing an optimal solution of the problem. Our primal algorithm iteratively updates primal variables by solving associated minimum cut problems. We show that the time complexity of the primal algorithm is O(K.T(n, m)), where K is the range of primal variables and T(n, m) is the time needed to compute a minimum cut in a graph with n nodes and m edges. We then develop an improved version of the primal algorithm, called the primal-dual algorithm, by making good use of dual variables in addition to primal variables. Although its time complexity is the same as that of the primal algorithm, we can expect a better performance in practice. We finally consider an application to a Computer vision problem called the panoramic image stitching. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Minimum cost tension Minimum cost flow discrete convex function Submodular function

来源：评论

学校读者我要写书评

暂无评论

M-convex functions on jump systems: A general framework for minsquare graph factor problem

引用

SIAM JOURNAL ON discrete MATHEMATICS 2006年第1期20卷 213-226页

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

The concept of M-convex functions is generalized for functions defined on constantparity jump systems. M-convex functions arise from minimum weight perfect b-matchings and from a separable convex function (sum of univariate convex functions) on the degree sequences of an undirected graph. As a generalization of a recent result of Apollonio and Sebo for the minsquare factor problem, a local optimality criterion is given for minimization of an M-convex function subject to a component sum constraint.

关键词： jump system degree sequence graph factor discrete convex function local optimality

来源：评论

学校读者我要写书评

暂无评论

A discrete convex Min-Max Formula for Box-TDI Polyhedra

引用

MATHEMATICS OF OPERATIONS RESEARCH 2022年第2期47卷 1026-1047页

作者： Frank, Andras Murota, Kazuo Eotvos Lorand Univ Dept Operat Res MTA ELTE Egervary Res Grp H-1117 Budapest Hungary Tokyo Metropolitan Univ Sch Business Adm Tokyo 1920397 Japan

A min-max formula is proved for the minimum of an integer-valued separable discrete convex function in which the minimum is taken over the set of integral elements of a box total dual integral polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in nonlinear optimization), but we also provide another version that avoids conjugates, and its spirit is conceptually closer to the standard form of classic min-max theorems in combinatorial optimization. The presented framework provides a unified background for separable convex minimization over the set of integral elements of the intersection of two integral base-polyhedra, submodular flows, L-convex sets, and polyhedra defined by totally unimodular matrices. As an unexpected application, we show how a wide class of inverse combinatorial optimization problems can be covered by this new framework.

关键词： min-max formula discrete convex function combinatorial inverse problem integral base-polyhedron M-convex set total dual integrality

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：