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

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

作者： Vegh, Laszlo A. London Sch Econ & Polit Sci Dept Management London England

ISBN: (纸本)9781450327107

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.

关键词： generalized flows strongly polynomial algorithms linear programming combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for image segmentation, Markov random fields and related problems

引用

JOURNAL OF THE ACM 2001年第4期48卷 686-701页

作者： Hochbaum, DS Univ Calif Berkeley Haas Sch Business Berkeley CA 94720 USA Univ Calif Berkeley Dept IE&OR Berkeley CA 94720 USA

Problems of statistical inference involve the adjustment of sample observations so they fit some a priori rank requirements, or order constraints. In such problems, the objective is to minimize the deviation cost function that depends on the distance between the observed value and the modify value. In Markov random field problems, there is also a pairwise relationship between the objects. The objective in Markov random field problem is to minimize the sum of the deviation cost function and a penalty function that grows with the distance between the values of related pairs-separation function. We discuss Markov random fields problems in the context of a representative application-the image segmentation problem. In this problem, the goal is to modify color shades assigned to pixels of an image so that the penalty function consisting of one term due to the deviation from the initial color shade and a second term that penalizes differences in assigned values to neighboring pixels is minimized. We present here an algorithm that solves the problem in polynomial time when the deviation function is convex and separation function is linear;and in strongly polynomial time when the deviation cost function is linear, quadratic or piecewise linear convex with few pieces (where "few" means a number exponential in a polynomial function of the number of variables and constraints). The complexity of the algorithm for a problem on n pixels or variables, m adjacency relations or constraints, and range of variable values (colors) U, is O(T (n, m) + n log U) where T (n, m) is the complexity of solving the minimum s, t cut problem on a graph with n nodes and m arcs. Furthermore, other algorithms are shown to solve the problem with convex deviation and convex separation in running time O (mn log n log n U) and the problem with nonconvex deviation and convex separation in running time 0(T (n U, m U). The nonconvex separation problem is NP-hard even for fixed value of U. For the family of p

关键词： algorithms convex optimization Markov random fields parametric minimum cut strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Inverse maximum flow problems under the weighted Hamming distance

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2006年第4期12卷 394-407页

作者： Liu, Longcheng Zhang, Jianzhong Zhejiang Univ Dept Math Hangzhou Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Hong Kong Hong Kong Peoples R China

In this paper, we consider inverse maximum flow problem under the weighted Hamming distance. Four models are studied: the problem under sum-type weighted Hamming distance;the problem under bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times.

关键词： maximum flow inverse problems Hamming distance strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Inverse min-max spanning tree problem under the Weighted sum-type Hamming distance

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期396卷 28-34页

作者： Liu, Longcheng Yao, Enyu Zhejiang Univ Dept Math Hangzhou Zhejiang Peoples R China

The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min-max spanning tree problem under the weighted sum-type Hamming distance. For the model considered, we present its combinatorial algorithm that runs in strongly polynomial times. (C) 2007 Elsevier B.V. All rights reserved.

关键词： min-max spanning tree inverse problem Hamming distance strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

TIGHT BOUNDS ON THE NUMBER OF MINIMUM-MEAN CYCLE CANCELLATIONS AND RELATED RESULTS

引用

ALGORITHMICA 1994年第3期11卷 226-242页

作者： RADZIK, T GOLDBERG, AV Computer Science Department Stanford University Stanford USA

We prove a tight Theta(min(nm log(nC), nm(2))) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations to O(nm(2)). We also give an improved version of the maximum-mean cut canceling algorithm of [7], which is a dual of the minimum-mean cycle-canceling algorithm. Our version of the dual algorithm runs in O(nm(2)) iterations.

关键词： NETWORK FLOW PROBLEMS MINIMUM COST FLOW MINIMUM COST CIRCULATION COMBINATORIAL OPTIMIZATION CYCLE CANCELING algorithms strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT algorithms FOR MINIMUM-COST FLOW PROBLEMS WITH PIECEWISE-LINEAR CONVEX COSTS

引用

ALGORITHMICA 1994年第3期11卷 256-277页

作者： PINTO, Y SHAMIR, R Department of Computer Science Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv Israel

We present two efficient algorithms for the minimum-cost flow problem in which are costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of linear are costs. Our first algorithm uses the Edmonds-Karp scaling technique. Its complexity is O(M log U(m + n log M)) for a network with n vertices, m arcs, M linear cost segments, and an upper bound U on the supplies and the capacities. The second algorithm is a strongly polynomial version of the first, and it uses Tardos's idea of contraction. Its complexity is O(M log M(m + n log M)). Both algorithms improve by a factor of at least Mim the complexity of directly applying existing algorithms to a transformed network in which are costs are linear.

关键词： MINIMUM-COST FLOW CONVEX COSTS MULTIPLE ARCS NETWORKS strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Inverse problems of submodular functions on digraphs

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2000年第3期104卷 559-575页

作者： Cai, M Yang, X Li, Y Chinese Acad Sci Inst Syst Sci Beijing Peoples R China Chinese Acad Sci Lab Management Decis & Informat Syst Beijing Peoples R China

In this paper, we study the inverse problem of submodular functions on digraphs. Given a feasible solution x* for a linear program generated by a submodular function defined on digraphs, we try to modify the coefficient vector c of the objective function, optimally and within bounds, such that x* becomes an optimal solution of the linear program. It is shown that the problem can be formulated as a combinatorial linear program and can be transformed further into a minimum cost circulation problem. Hence, it can be solved in strongly polynomial time. We also give a necessary and sufficient condition for the feasibility of the problem. Finally, we extend the discussion to the version of the inverse problem with multiple feasible solutions.

关键词： inverse problems submodular functions digraphs minimum cost circulation strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Constrained inverse minimum flow problems under the weighted Hamming distance

引用

THEORETICAL COMPUTER SCIENCE 2021年 883卷 59-68页

作者： Jiang, Yong Lin, Weifeng Liu, Longcheng Peng, Anzhen Fujian Agr & Forestry Univ Coll Comp & Informat Fuzhou 350002 Peoples R China Xiamen Univ Sch Math Sci Xiamen 361005 Peoples R China

In an inverse combinatorial optimization problem, a feasible solution is given and is not optimal under the current parameters. The aim is to make the feasible solution optimal by modifying the current parameters as little as possible. The modification cost can be measured by different norms, such as weighted l(1) norm, weighted l(2) norm, weighted l(infinity) norm, weighted Hamming distance and so on. In this paper, we focus on the constrained inverse minimum flow problems under the weighted Hamming distance. Three different models are considered: the general problem under the weighted bottleneck-type Hamming distance and two cases under the mixed of sum-type and bottleneck type. strongly polynomial algorithms are presented for the models we studied. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Minimum flow problem Inverse optimization problems Weighted Hamming distance strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimization with additional variables and constraints

引用

OPERATIONS RESEARCH LETTERS 2005年第3期33卷 305-311页

作者： Jüttner, A Eotvos Lorand Univ Dept Operat Res H-1117 Budapest Hungary Eotvos Lorand Univ Commun Networks Lab H-1117 Budapest Hungary

Norton, Plotkin and Tardos proved that-loosely spoken, an LP problem is solvable in time O(Tq(k+1)) if deleting k fixed columns or rows, we obtain a problem which can be solved by an algorithm that makes at most T steps and q comparisons. This paper improves this running time to O(Tq(k)). (C) 2004 Elsevier B.V. All rights reserved.

关键词： linear programming strongly polynomial algorithms parametric search

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：