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

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Dong, Sally Lee, Yin Tat Ye, Guanghao Univ Washington Seattle WA 98195 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781450380539

Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms. Many NP-hard problems are known to be solvable in (O) over tilde (n . 2(O(tau))) time, where tau is the treewidth of the input graph. Analogously, many problems in P should be solvable in (O) over tilde (n . tau(O(1))) time;however, due to the lack of appropriate tools, only a few such results are currently known. In our paper, we show this holds for linear programs: Given a linear program of the form min(Ax=b,l <= x <= u) c(T)x whose dual graph G(A) has treewidth tau, and a corresponding width-tau tree decomposition, we show how to solve it in time (O) over tilde (n . tau(2) log(1/epsilon)), where n is the number of variables and epsilon is the relative accuracy. When a tree decomposition is not given, we use existing techniques in vertex separators to obtain algorithms with (O) over tilde (n . tau(4)log(1/epsilon)) and (O) over tilde (n . tau(2)log(1/epsilon) + n(1.5)) run-times. Besides being the first of its kind, our algorithm has run-time nearly matching the fastest run-time for solving the sub-problem Ax = b (under the assumption that no fast matrix multiplication is used). We obtain these results by combining recent techniques in interior-point methods (IPMs), sketching, and a novel representation of the solution under a multiscale basis similar to the wavelet basis. This representation further yields the first IPM with o (rank(A)) time per iteration when the treewidth is small.

关键词： linear program interior point method treewidth parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Path-Finding Methods for linear programming Solving linear programs in (O)over-tilde(√rank) Iterations and Faster Algorithms for Maximum Flow 55

Path-Finding Methods for Linear Programming Solving Linear P...

引用

55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Lee, Yin Tat Sidford, Aaron MIT Dept Math Cambridge MA 02139 USA MIT Dept EECS Cambridge MA 02139 USA

ISBN: (纸本)9781479965175

In this paper, we present a new algorithm for solving linear programs that requires only (O) over tilde (root rank(A)L) iterations where A is the constraint matrix of a linear program with m constraints, n variables, and bit complexity L. Each iteration of our method consists of solving (O) over tilde (1) linear systems and additional nearly linear time computation. Our method improves upon the previous best iteration bounds by factor of (Omega) over tilde((m/rank (A)))(1/4)) for methods with polynomial time computable iterations and by (Omega) over tilde (m/rank (A)) 1/2) for methods which solve at most (O) over tilde (1) linear systems in each iteration each achieved over 20 years ago. Applying our techniques to the linear program formulation of maximum flow yields an (O) over tilde (vertical bar E vertical bar root vertical bar V vertical bar log(2) U) time algorithm for solving the maximum flow problem on directed graphs with vertical bar E vertical bar edges, vertical bar V vertical bar vertices, and capacity ratio U. This improves upon the previous fastest running time of O(vertical bar E vertical bar min{vertical bar E vertical bar(1/2), vertical bar V vertical bar(2/3)} log(vertical bar V vertical bar(2)/vertical bar E vertical bar) log(U)) achieved over 15 years ago by Goldberg and Rao and improves upon the previous best running times for solving dense directed unit capacity graphs of O(vertical bar E vertical bar min{vertical bar E vertical bar(1/2), vertical bar V vertical bar(2/3)}) achieved by Even and Tarjan over 35 years ago and a running time of O(vertical bar E vertical bar(10/7)) achieved recently by Madry.

关键词： linear program maximum flow interior point

来源：评论

学校读者我要写书评

暂无评论

Blind separation of non-negative sources by convex analysis: Effective method using linear programming

Blind separation of non-negative sources by convex analysis:...

引用

33rd IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Chan, Tsung-Han Ma, Wing-Kin Chi, Chong-Yung Wang, Yue Natl Tsing Hua Univ Inst Commun Engn Hsinchu Taiwan Chinese Univ Hong Kong Dept Elect Engn Hong Kong Peoples R China State Univ Virginia Tech Inst Dept Elect & Comp Biomed Engn Arlington VA 22303 USA

ISBN: (纸本)9781424414833

We recently reported a criterion for blind separation of non-negative sources, using a new concept called convex analysis for mixtures of non-negative sources (CAMNS). Under some assumptions that are considered realistic for sparse or high-contrast signals, the criterion is that the true source signals can be perfectly recovered by finding the extreme points of some observation-constructed convex set. In our last work we also developed methods for fulfilling the CAMNS criterion, but only for two to three sources. In this paper we propose a systematic linear programming (LP) based method that is applicable to any number of sources. The proposed method has two advantages. First, its dependence on LP means that the method does not suffer from local minima. Second, the maturity of LP solvers enables efficient implementation of the proposed method in practice. Simulation results are provided to demonstrate the efficacy of the proposed method.

关键词： blind separation non-negative sources convex analysis criterion linear program

来源：评论

学校读者我要写书评

暂无评论

Sparse object reconstruction from a limited number of projections using the linear programming

Sparse object reconstruction from a limited number of projec...

引用

IEEE Nuclear Science Symposium/Medical Imaging Conference (NSS/MIC)

作者： Li, MH Kudo, H Hu, J Johnson, R Univ Tsukuba Doctoral Program Engn Tsukuba Ibaraki 3058573 Japan

ISBN: (纸本)0780376366

This paper proposes a simple row-action type iterative algorithm which is appropriate to reconstruct sparse objects from a limited number of projections. The main idea is to use the L-1 norm to pick up a sparse solution from a set of feasible solutions to the measurement equation. By perturbing the linear program to a quadratic program, we use the duality of the nonlinear programming to construct a row-action type iterative algorithm to find a solution, we also prove that the algorithm converges for any initial image. We show that this method works well in the 3D blood-vessel reconstruction and its computation time is shorter compared to our previous method.

关键词： sparsity linear program perturbation duality

来源：评论

学校读者我要写书评

暂无评论

Solving linear programs in the Current Matrix Multiplication Time 2019

Solving Linear Programs in the Current Matrix Multiplication...

引用

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

作者： Cohen, Michael B. Lee, Yin Tat Song, Zhao MIT Cambridge MA 02139 USA Microsoft Res Redmond WA 98052 USA Univ Washington Seattle WA 98195 USA UT Austin Austin TX USA

ISBN: (纸本)9781450367059

This paper shows how to solve linear programs of the form min(Ax=b, x >= 0) c (inverted perpendicular) x with n variables in time O*((n(omega) + n(2.5-alpha/2) + n(2+1/6)) log(n/delta)) where omega is the exponent of matrix multiplication, alpha is the dual exponent of matrix multiplication, and delta is the relative accuracy. For the current value of omega similar to 2.37 and alpha similar to 0.31, our algorithm takes O*(n(omega) log(n/delta)) time. When omega = 2, our algorithm takes O*(n(2+1/6) log(n/delta)) time. Our algorithm utilizes several new concepts that we believe may be of independent interest: (1) We define a stochastic central path method. (2) We show how to maintain a projection matrix root WA(inverted perpendicular)(AWA(inverted perpendicular))(-1)A root W in sub-quadratic time under l(2) multiplicative changes in the diagonal matrix W.

关键词： linear program interior point method matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Algorithm 431: A Computer Routine for Quadratic and linear programming Problems [H]

引用

Communications of the ACM 1972年第9期15卷 818-820页

作者： Ravindran, Arunachalam Purdue University Lafayette IN 47907 United States

A computer program based on Lemke's complementary pivot algorithm is presented. This can be used to solve linear and quadratic programming problems. The program has been extensively tested on a wide range of probl... 详细信息

关键词： complementary problem Lemke's algorithm linear program quadratic program simplex method

来源：评论

学校读者我要写书评

暂无评论

CUSTOMIZATION OF ALGORITHM FOR PROGRESSIVE linear-programS (PROLP) USING NEURAL-NET WORK

引用

KAGAKU KOGAKU RONBUNSHU 1995年第3期21卷 614-617页

作者： SHIMIZU, Y Research Reactor Institute Kyoto University Sennan-gun 590-04 Japan

In chemical processes, we often take advantage of customizing daily problem-solving when a final solution will be obtained after solving a family of optimization problems repeatedly. In aid of the neural network, in this note we have engaged in improving and customizing the algorithm of progressive linear programs (PROLP) after introducing manifold criteria to estimate active constraints. Through a few numerical experiments, the effect of the approach has been examined.

关键词： PROCESS SYSTEM linear program NEURAL NET WORK CUSTOMIZATION OF PROLP

来源：评论

学校读者我要写书评

暂无评论

PROGRESSIVE APPLICATION OF linear-programS CONCERNING WITH PROBLEM-SOLVING IN CHEMICAL PROCESSES - DEVELOPMENT AND APPLICATION OF PROLP

引用

KAGAKU KOGAKU RONBUNSHU 1995年第3期21卷 521-530页

作者： SHIMIZU, Y Research Reactor Institute Kyoto University Sennan-gun 590-04 Japan

linear programs (LP) have been used popularly as practical optimization methods in many fields for many years. Due to the recent diversification of problem-solving, however, the problem must be formulated in a difficult and complicated manner. It is thus necessary to develop special methods that can solve large complex LP effectively as well as flexibly. A new approach for the simplex method, termed PAPA (pivot and probe algorithm), is considered promising for such situations. Since its effectiveness is confined to a special form of problem, we generalized it in this paper by applying a dual algorithm in the framework of the two-phase method for LP solution. In comparison with the revised simplex method, we examined numerically its efficiency by solving a variety of randomly generated test problems. Then, we paid special attention to application of the method in chemical processes. Thereupon, we pointed out the proposed method is especially effective where certain reference information is available to solve a family of problems repeatedly before arriving at a final result. This is why we propose calling the method ''progressive linear programs'' (PROLP).

关键词： PROCESS SYSTEM linear program PIVOT AND PROBE ALGORITHM MULTIOBJECTIVE PLANNING PROBLEM REDESIGN PROBLEM MODEL PREDICTIVE CONTROL

来源：评论

学校读者我要写书评

暂无评论

Efficient Computation of User Optimal Traffic Assignment via Second-Order Cone and linear programming Techniques

引用

IEEE ACCESS 2019年 7卷 137010-137019页

作者： Wei, Wei Hu, Longxian Wu, Qiuwei Ding, Tao Tsinghua Univ Dept Elect Engn State Key Lab Power Syst Beijing 100084 Peoples R China Tech Univ Denmark Dept Elect Engn DK-2800 Lyngby Denmark Xi An Jiao Tong Univ Dept Elect Engn Xian 710049 Shaanxi Peoples R China

Static traffic assignment aims to disclose the spatial distribution of vehicular flow over a transportation network subject to given traffic demands, and plays an essential role in transportation engineering. User-optimal pattern adheres the individual rationality of motorists, in which everyone chooses a route that minimizes his own travel cost, while considering congestion effects influenced by the aggregated movement of vehicles. User optimal traffic assignment, which is also known as the user equilibrium, entails solving an optimization problem with a strictly convex objective function and linear constraints. However, the performances of general-purpose solvers are quite disappointing. This paper proposes two highly efficient computation models for the user equilibrium problem. The first one exploits the second-order cone reformulation of a convex power function, resulting in a second-order cone program, and no approximation is incurred. The second one approximates the convex objective function using a piece-wise linear function, and comes down to a linear program. An adaptive path generation oracle is devised in order to circumvent path enumeration in problem setup. Case studies demonstrate that the proposed method can deal with large-scale transportation systems, and outperforms the most popular iterative algorithm in the literature.

关键词： linear program second-order cone program traffic assignment user equilibrium

来源：评论

学校读者我要写书评

暂无评论

Quadratic diameter bounds for dual network flow polyhedra

引用

MATHEMATICAL programMING 2016年第1-2期159卷 237-251页

作者： Borgwardt, Steffen Finhold, Elisabeth Hemmecke, Raymond Tech Univ Munich Munich Germany

Both the combinatorial and the circuit diameter of polyhedra are of interest to the theory of linear programming for their intimate connection to a best-case performance of linear programming algorithms. We study the diameters of dual network flow polyhedra associated to b-flows on directed graphs and prove quadratic upper bounds for both of them: the minimum of and for the combinatorial diameter, and for the circuit diameter. Previously, bounds on these diameters have only been known for bipartite graphs. The situation is much more involved for general graphs. In particular, we construct a family of dual network flow polyhedra with members that violate the circuit diameter bound for bipartite graphs by an arbitrary additive constant.

关键词： Combinatorial diameter Circuit diameter Hirsch conjecture Edges Circuits Graver basis linear program Integer program

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：