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

A Strongly Polynomial Algorithm for Generalized flow Maximization

MATHEMATICS OF OPERATIONS RESEARCH 2017年第1期42卷 179-211页

作者： Vegh, Laszlo A. London Sch Econ & Polit Sci Dept Math London WC2A 2AE England

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. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per column in the constraint matrix.

关键词： network flow algorithms generalized flows strongly polynomial algorithms linear programming

来源：评论

学校读者我要写书评

暂无评论

Concave Generalized flows with Applications to Market Equilibria

引用

MATHEMATICS OF OPERATIONS RESEARCH 2014年第2期39卷 573-596页

作者： Vegh, Laszlo A. London Sch Econ Dept Management London WC2A 2AE England

We consider a nonlinear extension of the generalized network flow model, with the flow leaving an arc being an increasing concave function of the flow entering it, as proposed by Truemper [Truemper K (1978) Optimal flows in nonlinear gain networks. networks 8(1): 17-36] and by Shigeno [Shigeno M (2006) Maximum network flows with concave gains. Math. Programming 107(3): 439-459]. We give a polynomial time combinatorial algorithm for solving corresponding flow maximization problems, finding an epsilon-approximate solution in O(m(m sigma+log n) log (MUm/epsilon)) arithmetic operations, where M and U are upper bounds on simple parameters, and sigma is the complexity of a value oracle query for the gain functions. This also gives a new algorithm for linear generalized flows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg et al. [Goldberg AV, Plotkin SA, Tardos E (1991) Combinatorial algorithms for the generalized circulation problem. Math. Oper. Res. 16(2):351-381], not using any cycle cancellations. We show that this general convex programming model serves as a common framework for several market equilibrium problems, including the linear Fisher market model and its various extensions. Our result immediately provides combinatorial algorithms for various extensions of these market models. This includes nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani [Vazirani VV (2012) The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. J. ACM 59(2), Article 7].

关键词： network flow algorithms generalized flows convex programming market equilibrium

来源：评论

学校读者我要写书评

暂无评论

Scheduling jobs on several machines with the job splitting property

引用

OPERATIONS RESEARCH 1996年第4期44卷 617-628页

作者： Serafini, P UNIV UDINE DEPT MATH & COMP SCII-33100 UDINEITALY

This scheduling model is derived from the real problem of scheduling looms in a textile industry. Jobs may be independently split. over several specified machines, and preemption is allowed. Deadlines are specified for each job, and jobs are assumed to be available. It is shown that minimizing maximum weighted tardiness can be done in polynomial time. The case of uniform machines (as in the considered application) can be modeled as a network flow, and minimization of maximum tardiness can be done in strongly polynomial time. The case of unrelated machines can be solved either by generalized flow techniques or by Linear Programming. Attention is also focused on the problem of finding so-called Unordered Lexico Optima, in order to schedule nonbinding jobs as early as possible.

关键词： industries textiles model for loom scheduling network flow algorithms application to scheduling scheduling sequencing multiple machines

来源：评论

学校读者我要写书评

暂无评论

A STRONGLY POLYNOMIAL ALGORITHM FOR A CLASS OF MINIMUM-COST flow PROBLEMS WITH SEPARABLE CONVEX OBJECTIVES

引用

SIAM JOURNAL ON COMPUTING 2016年第5期45卷 1729-1761页

作者： Vegh, Laszlo A. London Sch Econ Dept Math London WC2A 2AE England

A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective Sigma(ij is an element of Epsilon) 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 the case when all C-ij's are convex quadratic functions, settling an open problem raised, e.g., by Hochbaum [Math. Oper. Res., 19 (1994), pp. 390-409]. We also give strongly polynomial algorithms for computing market equilibria in Fisher markets with linear utilities and with spending constraint utilities that can be formulated in this framework (see Shmyrev [J. Appl. Ind. Math., 3 (2009), pp. 505-518], Birnbaum, Devanur, and Xiao [Proceedings of the 12th ACM Conference on Electronic Commerce, 2011, pp. 127-136]). For the latter class this resolves an open question raised by Vazirani [Math. Oper. Res., 35 (2010), pp. 458-478]. 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) logm) for spending constraint utilities. All these algorithms are presented in a common framework that addresses the general problem setting. Whereas it is impossible to give a strongly polynomial algorithm for the general problem even in an approximate sense (see Hochbaum [Math. Oper. Res., 19 (1994), pp. 390-409]), we show that assuming the existence of certain black-box oracles, one can give an algorithm using a strongly polynomial number of arithmetic operations and oracle calls only. The particular algorithms can be derived by implementing these oracles in the respective settings.

关键词： network flow algorithms convex optimization strongly polynomial algorithms market equilibrium computation

来源：评论

学校读者我要写书评

暂无评论

Simple linear flow decomposition algorithms on trees, circles, and augmented trees

引用

networkS 2012年第4期60卷 227-234页

作者： Vaidyanathan, Balachandran FedEx Express Operat Res Memphis TN 38125 USA

The flow decomposition algorithm transforms an arc flow-based solution to a network flow problem into flows on directed paths and cycles. When the undirected graph induced by arcs with positive flow is a tree, a circle, or an augmented tree (with n nodes), the standard implementation of the algorithm runs in O(n(2)) time. In this article, we exploit the structure of the network to develop an O(n) flow decomposition algorithm. The run-time relies on the property that for these networks, paths or cycles can be represented implicitly in O(1) space. The algorithm is easy to implement and does not use complicated data structures. Because the size of the input is O(n), our algorithm is the fastest possible for flow decomposition on these special networks. Our algorithm can be used to improve run-times for solving matching and transportation problems on trees and circles. (c) 2012 Wiley Periodicals, Inc. networkS, Vol. 60(4), 227-234 2012

关键词： network flow algorithms flow decomposition complexity analysis trees circles augmented trees

来源：评论

学校读者我要写书评

暂无评论

Convex generalized flows

引用

DISCRETE APPLIED MATHEMATICS 2015年 190卷 86-99页

作者： Holzhauser, Michael Krumke, Sven O. Thielen, Clemens Univ Kaiserslautern Dept Math D-67663 Kaiserslautern Germany

We study an extension of the well-known generalized maximum flow problem in which the outflow of an edge is a strictly increasing convex function of its inflow. In contrast to the traditional generalized maximum flow problem, in which the outflow of an edge depends linearly on its inflow and which is solvable in polynomial time, we show that, for convex outflow functions, the problem becomes strongly NP-hard to solve even on bipartite acyclic graphs and weakly NP-hard on series-parallel graphs, Both results hold even if the outflow functions are convex quadratic. Furthermore, we present (exponentialtime) exact algorithms for computing optimal flows on acyclic and series parallel graphs and optimal preflows on general graphs. We also show that a flow decomposition similar to the one for traditional generalized flows is possible and present a pseudo-polynomial-time algorithm for the case of integral flows on series parallel graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： network flow algorithms Generalized flows Maximum flows Computational complexity flow decomposition

来源：评论

学校读者我要写书评

暂无评论

A SHORT-TERM HYDROTHERMAL SCHEDULING APPROACH FOR DOMINANTLY HYDRO SYSTEMS

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 1991年第2期6卷 637-643页

作者： OHISHI, T SOARES, S CARVALHO, MFH TECHNOL INFORMAT CTR BR-13081 CAMPINASSPBRAZIL

This paper presents a short term hydrothermal scheduling approach for dominantly hydro systems. The problem modelling takes into account both the hydroelectric system operating and the electric transmission network constraints in detail. It basically consists of a simulation of the hydraulic system with the discharge decisions given by an optimal DC power flow algorithm. The release targets of the reservoirs, established by the long term operational planning, are enforced by a dual Lagrangean approach that fixes a penalty for the use of water in the reservoirs. Two illustrative examples have been solved in order to evaluate the efficiency of the approach.

关键词： HYDROTHERMAL SCHEDULING SHORT TERM OPERATING PLANNING DOMINANTLY HYDRO SYSTEMS SIMULATION OPTIMIZATION DC LOAD flow network flow algorithms

来源：评论

学校读者我要写书评

暂无评论

Fairness and efficiency in pedestrian emergency evacuation: Modeling and simulation

引用

SAFETY SCIENCE 2020年 121卷 373-384页

作者： Aalami, Soheila Kattan, Lina Univ Calgary Dept Civil Engn Calgary AB Canada

The goal of this paper is to study different algorithms for planning a large scale pedestrian evacuation process. A pedestrian (walking) mode of evacuation is an efficient mode of transportation that is often overlooked in the literature. Fairness in the evacuation process is another aspect that is rarely studied. In this paper, we study efficiency and fairness of pedestrian mode of emergency evacuation. We model the evacuation problem as a dynamic network flow problem, which captures the time-dependency of the network attributes such as edge and vertex capacities and edge travel times. To evaluate the efficiency of the algorithms, we consider the clearance time of the network. To investigate fairness, we consider the Gini coefficient and Lorenz curve that are popular indexes in economy to measure wealth distribution in a society. We compute the Gini coefficient and Lorenz curve to measure the fairness in travel time distribution of the evacuees in the emergency evacuation process. We develop a new algorithm called PEPA (Pedestrian Evacuation Planning Algorithm) to find the minimum clearance time of the network. PEPA is compared to two commonly studied graph algorithms in the literature, shortest path and maximum flow algorithms. We compared the algorithms in terms of computation time of the algorithm, clearance time of the network and Gini coefficient. Our results show that PEPA beats both shortest path and maximum flow in terms of efficiency and fairness, although it is slightly slower in terms of computation time. To implement PEPA, shortest path and maximum flow algorithms, we develop a new software named PEMSS (Pedestrian Evacuation Modeler, Solver, and Simulator). PEMSS is written in the Java programming language and is capable of reading and showing maps in open street map XML format.

关键词： Large scale pedestrian evacuation Urban area evacuation network flow algorithms Software Simulation

来源：评论

学校读者我要写书评

暂无评论

A competitive study of the pseudoflow algorithm for the minimum s-t cut problem in vision applications

引用

JOURNAL OF REAL-TIME IMAGE PROCESSING 2016年第3期11卷 589-609页

作者： Fishbain, B. Hochbaum, Dorit S. Mueller, Stefan Technion Israel Inst Technol IL-32000 Haifa Israel Univ Calif Berkeley Berkeley CA 94720 USA Tech Univ Berlin Berlin Germany

Rapid advances in image acquisition and storage technology underline the need for real-time algorithms that are capable of solving large-scale image processing and computer-vision problems. The minimum s-t cut problem, which is a classical combinatorial optimization problem, is a prominent building block in many vision and imaging algorithms such as video segmentation, co-segmentation, stereo vision, multi-view reconstruction, and surface fitting to name a few. That is why finding a real-time algorithm which optimally solves this problem is of great importance. In this paper, we introduce to computer vision the Hochbaum's pseudoflow (HPF) algorithm, which optimally solves the minimum s-t cut problem. We compare the performance of HPF, in terms of execution times and memory utilization, with three leading published algorithms: (1) Goldberg's and Tarjan's Push-Relabel;(2) Boykov's and Kolmogorov's augmenting paths;and (3) Goldberg's partial augment-relabel. While the common practice in computer-vision is to use either BK or PRF algorithms for solving the problem, our results demonstrate that, in general, HPF algorithm is more efficient and utilizes less memory than these three algorithms. This strongly suggests that HPF is a great option for many real-time computer-vision problems that require solving the minimum s-t cut problem.

关键词： network flow algorithms Maximum-flow Minimum-cut Segmentation Stereo vision Multi-view reconstruction Surface fitting

来源：评论

学校读者我要写书评

暂无评论

Adaptive Multiscale Complexity Analysis of Fetal Heart Rate

引用

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING 2011年第8期58卷 p2186-2193页

作者： Helgason, H. Abry, P. Goncalves, P. Gharib, Cl. Gaucherand, P. Doret, M. KTH Sch Elect Engn SE-10044 Stockholm Sweden Ecole Normale Super Lyon CNRS Dept Phys F-69364 Lyon France Ecole Normale Super Lyon INRIA Dept Comp Sci F-69364 Lyon France Univ Lyon Hop Femme Mere Enfant Hosp Civils Lyon F-69364 Lyon France

Per partum fetal asphyxia is a major cause of neonatal morbidity and mortality. Fetal heart rate monitoring plays an important role in early detection of acidosis, an indicator for asphyxia. This problem is addressed in this paper by introducing a novel complexity analysis of fetal heart rate data, based on producing a collection of piecewise linear approximations of varying dimensions from which a measure of complexity is extracted. This procedure specifically accounts for the highly nonstationary context of labor by being adaptive and multiscale. Using a reference dataset, made of real per partum fetal heart rate data, collected in situ and carefully constituted by obstetricians, the behavior of the proposed approach is analyzed and illustrated. Its performance is evaluated in terms of the rate of correct acidosis detection versus the rate of false detection, as well as how early the detection is made. Computational cost is also discussed. The results are shown to be extremely promising and further potential uses of the tool are discussed. MATLAB routines implementing the procedure will be made available at the time of publication.

关键词： Fetal heart rate (FHR) monitoring multiscale approximations network flow algorithms per partum acidosis detection time series complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：