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

Constrained inverse min-max spanning tree problems under the weighted Hamming distance

JOURNAL OF GLOBAL OPTIMIZATION 2009年第1期43卷 83-95页

作者： Liu, Longcheng Wang, Qin Zhejiang Univ Dept Math Hangzhou 310003 Zhejiang Peoples R China China Jiliang Univ Dept Math Hangzhou Zhejiang Peoples R China

In this paper, we consider the constrained inverse min-max spanning tree problems under the weighted Hamming distance. Three models are studied: the problem under the bottleneck-type weighted Hamming distance and two mixed types of problems. We present their respective combinatorial algorithms that all run in strongly polynomial times.

关键词： Min-max spanning tree Inverse problems 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

来源：评论

学校读者我要写书评

暂无评论

IMPROVED algorithms FOR LINEAR INEQUALITIES WITH 2 VARIABLES PER INEQUALITY

引用

SIAM JOURNAL ON COMPUTING 1994年第6期23卷 1313-1347页

作者： COHEN, E MEGIDDO, N STANFORD UNIV STANFORD CA 94305 USA IBM RES CORP ALMADEN RES CTR SAN JOSE CA 95120 USA TEL AVIV UNIV SCH MATH SCI IL-69978 TEL AVIV ISRAEL

The authors show that a system of m linear inequalities with n variables, where each inequality involves at most two variables, can be solved in ($) over tilde O (mn(2)) time (we denote ($) over tilde O(f) = O(f polylog n polylog m)) deterministically, and in ($) over tilde O(n(3) + mn) expected time using randomization. parallel implementations of these algorithms run in ($) over tilde O(n) time, where the deterministic algorithm uses ($) over tilde O)(mn) processors and the randomized algorithm uses ($) over tilde On(2) + m) processors. The bounds significantly improve over previous algorithms. The randomized algorithm is based on novel insights into the structure of the problem.

关键词： LINEAR INEQUALITIES 2-VARIABLES INEQUALITIES LINEAR SYSTEMS LINEAR PROGRAMMING strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Complexity and algorithms for nonlinear optimization problems

引用

ANNALS OF OPERATIONS RESEARCH 2007年第1期153卷 257-296页

作者： Hochbaum, Dorit S. Univ Calif Berkeley Dept Ind Engn & Operat Res Berkeley CA 94720 USA Univ Calif Berkeley Walter A Haas Sch Business Berkeley CA 94720 USA

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization.

关键词： nonlinear optimization convex network flow strongly polynomial algorithms lower bounds on complexity

来源：评论

学校读者我要写书评

暂无评论

Characterization sets for the nucleolus

引用

INTERNATIONAL JOURNAL OF GAME THEORY 1998年第3期27卷 359-374页

作者： Granot, D Granot, F Zhu, WR Univ British Columbia Fac Commerce & Business Adm Vancouver BC V6T 1Z2 Canada

We introduce the concept of a characterization set for the nucleolus of a cooperative game and develop sufficient conditions for a collection of coalitions to form a characterization set thereof. Further, we formalize Kopelowitz's method for computing the nucleolus through the notion of a sequential LP process, and derive a general relationship between the size of a characterization set and the complexity of computing the nucleolus.

关键词： cooperative game nucleolus strongly polynomial algorithms minimum cost spanning tree games

来源：评论

学校读者我要写书评

暂无评论

New polynomial-time cycle-canceling algorithms for minimum-cast flows

引用

NETWORKS 2000年第1期36卷 53-63页

作者： Sokkalingam, PT Ahuja, RK Orlin, JB Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA ODC Ctr CISCO HCL Chennai India MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

The cycle-canceling algorithm is one of the earliest algorithms to solve the minimum-cost flow problem. This algorithm maintains a feasible solution x in the network G and proceeds by augmenting flows along negative-cost directed cycles in the residual network G(x) and thereby canceling them. For the minimum-cost flow problem with integral data, the generic version of the cycle-canceling algorithm runs in pseudopolynomial time, but several polynomial-time specific implementations can be obtained by specifying the choices of cycles to be canceled. In this paper, we describe a new polynomial-time implementation of the cycle-canceling algorithm. Our algorithm is a scaling algorithm and proceeds by augmenting flows along negative cycles with "sufficiently large" residual capacity. Further, it identifies such a cycle by solving a shortest path problem with nonnegative are lengths. For a network with n nodes and m arcs, our cycle-canceling algorithm performs O(m log(nU)) augmentations and runs in O(m(m + n log n) log (nU)) time, where U is an upper bound on the node supplies/demands and finite are capacities. We also show that the cycle-canceling algorithm (i) can solve the uncapacitated minimum-cost flow problem in O(n(m + n log n) log (nU)) time;(ii) can obtain an integer optimal solution of the convex cost-flow problem in O(m(m + n log n) log (nU)) time;and (iii) can be modified so that it runs in O(m(m + n log n) min (log (nU), m log n)) time, which is a strongly polynomial time bound. (C) 2000 John Wiley & Sons, Inc.

关键词： minimum-cost flow problem convex cost-flow problem cycle-canceling algorithm strongly polynomial algorithms scaling algorithms network flows

来源：评论

学校读者我要写书评

暂无评论

Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max 2019

Approximating APSP without Scaling: Equivalence of Approxima...

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Bringmann, Karl Kuennemann, Marvin Wegrzycki, Karol Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9781450367059

Zwick's (1 + epsilon)-approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time O(n(omega)/epsilon log W), where omega <= 2.373 is the exponent of matrix multiplication andW denotes the largest weight. This can be used to approximate several graph characteristics including the diameter, radius, median, minimum-weight triangle, and minimum-weight cycle in the same time bound. Since Zwick's algorithm uses the scaling technique, it has a factor log W in the running time. In this paper, we study whether APSP and related problems admit approximation schemes avoiding the scaling technique. That is, the number of arithmetic operations should be independent of W;this is called strongly polynomial. Our main results are as follows. (1) We design approximation schemes in strongly polynomial time O(n(omega)/epsilon polylog(n/epsilon)) for APSP on undirected graphs as well as for the graph characteristics diameter, radius, median, minimum-weight triangle, and minimum-weight cycle on directed or undirected graphs. (2) For APSP on directed graphs we design an approximation scheme in strongly polynomial time O(n omega+3/2 epsilon(-1) polylog(n/epsilon)). This is significantly faster than the best exact algorithm. (3) We explain why our approximation scheme for APSP on directed graphs has a worse exponent than omega: Any improvement over our exponent omega+3/2 would improve the best known algorithm for Min-Max Product. In fact, we prove that approximating directed APSP and exactly computing the Min-Max Product are equivalent. Our techniques yield a framework for approximation problems over the (min,+)-semiring that can be applied more generally. In particular, we obtain the first strongly polynomial approximation scheme for Min-Plus Convolution in strongly subquadratic time, and we prove an equivalence of approximate Min-Plus Convolution and exact Min-Max Convolution.

关键词： strongly polynomial algorithms approximation schemes hardness of approximation fine-grained complexity

来源：评论

学校读者我要写书评

暂无评论

Complexity and algorithms for convex network optimization and other nonlinear problems

引用

4OR 2005年第3期3卷 171-216页

作者： Hochbaum, Dorit S. Department of Industrial Engineering and Operations Research Walter A. Haas School of Business University of California Berkeley 94720 United States

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. © Springer-Verlag 2005.

关键词： Convex network flow Lower bounds on complexity Nonlinear optimization strongly polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Inverse min-max spanning tree problem under the weighted sum-type hamming distance

引用

1st International Conference on Combinatorics, algorithms, Probabilistic and Experimental Methodologies

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

ISBN: (纸本)9783540744498

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 run in strongly polynomial times.

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

来源：评论

学校读者我要写书评

暂无评论

Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers 61

Revisiting Tardos's Framework for Linear Programming: Faster...

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Dadush, Daniel Natura, Bento Vegh, Laszlo A. Ctr Wiskunde & Informat Networks & Optimizat Grp Amsterdam Netherlands London Sch Econ & Polit Sci Dept Math London England

ISBN: (纸本)9781728196213

In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based framework for solving linear programming (LP) in time depending only on the constraint matrix in the bit complexity model. In Tardos's framework, one reduces solving the LP min < c, x >, Ax = b, x >= 0, A is an element of Z(mxn), to solving O(nm) LPs in A having small integer coefficient objectives and right-hand sides using any exact LP algorithm. This gives rise to an LP algorithm in time poly(n, mlog Delta A), where Delta A is the largest subdeterminant of A. A significant extension to the real model of computation was given by Vavasis and Ye (Math. Prog. '96), giving a specialized interior point method that runs in time poly(n, m, log (chi) over barA), depending on Stewart's (chi) over barA), a wellstudied condition number. In this work, we extend Tardos's original framework to obtain such a running time dependence. In particular, we replace the exact LP solves with approximate ones, enabling us to directly leverage the tremendous recent algorithmic progress for approximate linear programming. More precisely, we show that the fundamental "accuracy" needed to exactly solve any LP in A is inverse polynomial in n and log (chi) over bar (A). Plugging in the recent algorithm of van den Brand (SODA '20), our method computes an optimal primal and dual solution using O((mn omega+1+o(1)) log((chi) over barA+n)) arithmetic operations, outperforming the specialized interior point method of Vavasis and Ye and its recent improvement by Dadush et al (STOC '20). By applying the preprocessing algorithm of the latter paper, the dependence can also be reduced from (chi) over barA to (chi) over bar *A, the minimum value of .AD attainable via column rescalings. Our framework is applicable to achieve the poly(n, m, log (chi) over bar.* A) bound using essentially any weakly polynomial LP algorithm, such as the ellipsoid method. At a technical level, our framework combines together approximate LP solutions

关键词： linear programming strongly polynomial algorithms condition numbers proximity circuits

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：