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

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

来源：评论

学校读者我要写书评

暂无评论

A Branch-and-Bound Algorithm for Representative Integer Efficient Solutions in Multiple Objective network Programming Problems

引用

networkS 2013年第1期62卷 56-71页

作者： Sun, Minghe Univ Texas San Antonio Dept Management Sci & Stat Coll Business San Antonio TX 78249 USA

In many applications of multiple objective network programming (MONP) problems, only integer solutions are acceptable as the final optimal solution. Representative efficient solutions are usually obtained by sampling the efficient set through the solution of augmented weighted Tchebycheff network programs. Because such efficient solutions are usually not integer solutions, a branch-and-bound (BB) algorithm is developed to find integer efficient solutions. The purpose of the BB algorithm is to support interactive procedures by generating representative integer efficient solutions. To be computationally efficient, the algorithm takes advantage of the network structure as much as possible. An algorithm, used in the BB algorithm and performed on the key tree, is developed to construct feasible solutions from infeasible solutions and basic solutions from nonbasic solutions when bounds on branching variables change. The BB algorithm finds basic and nonbasic or supported and unsupported integer efficient solutions as long as they are optimal. Details of the algorithm are presented, an example is provided and computational results are reported. Computational results show that the BB algorithm performs well. Although the BB algorithm is developed for the purpose of generating integer efficient solutions for MONP problems, it can also solve more general integer network flow problems with linear side constraints. (c) 2013 Wiley Periodicals, Inc.

关键词： network flow algorithms multiple objective programming multiple criteria decision making integer programming branch-and-bound network flow problems with side constraints

来源：评论

学校读者我要写书评

暂无评论

network flow Interpretation of Innovation Processes and Risks

Network Flow Interpretation of Innovation Processes and Risk...

引用

Signal Processing Symposium (SPS)

作者： Sgurev, Vassil S. Doukovska, Lyubka A. Drangajov, Stanislav T. Nikov, Vassil G. Bulgarian Acad Sci Inst Informat & Commun Technol BU-1113 Sofia Bulgaria

ISBN: (纸本)9781467363198

The innovation processes are connected with uncertainty and considerable financial risk. No matter whether a new product, technology or methodology is promoted, there are several stages that the innovation passes. The first three are connected with venture investments and the final - with eventual good profits. It is possible that the outcome is a failure, which is normal for any venture enterprise. Convenient tools for modeling the introduction of an innovation are the network flow models which turn to be fairly adequate and to provide reliable data to the decision maker. It is to be noted that the process is unidirectional, i.e., it cannot go to back stages, the underlying graph is a directed acyclic one and this structure is of increasing interest in the research area. The work is illustrated by a numerical example which demonstrates the relevancy of the network flow model.

关键词： network flow algorithms innovation management

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for Convex Cost flow Problems on Circles, Lines, and Trees

引用

networkS 2013年第4期62卷 288-296页

作者： Orlin, James B. Vaidyanathan, Balachandran MIT Sloan Sch Management Cambridge MA 02139 USA FedEx Express Operat Res Memphis TN 38125 USA

We develop efficient algorithms to solve convex cost flow problems where the underlying graph is a circle, a line, or a tree. Each node i has an associated supply/demand b( i). The cost of sending flow on arc ( i, j) is a piecewise linear convex function f(ij) defined over . Let n be the number of nodes and m = O(n) be the total number of pieces of all the convex functions. A flow x is feasible if the imbalances on all nodes are nonnegative. Excess ei(x) stored on node i has an associated linear cost cixei(x). We show that the problem on a circle can be transformed into an equivalent problem on a line in O( n) time. Thereafter, we develop an algorithm that solves the problem on a line in O(sort(n)+n(n)) time, where sort( n) is the time to sort n real numbers and (n) is the inverse Ackermann function. We also prove that when the nodes lie on a tree, the problem can be solved in O(nlog?n) time using the dynamic tree data structure. We describe applications in areas such as distributed computing, lot-sizing, computational biology, computational music, and transportation. (c) 2013 Wiley Periodicals, Inc. networkS, Vol. 62(4), 288-296 2013

关键词： network flow algorithms convex cost flows minimum cost flows computational complexity applications

来源：评论

学校读者我要写书评

暂无评论

Real-time, Robust Target Tracking in Videos via Graph-cuts

Real-time, Robust Target Tracking in Videos via Graph-cuts

引用

Conference on Real-Time Image and Video Processing

作者： Fishbain, Barak Hochbaum, Dorit S. Yang, Yan T. Technion Israel Inst Technol Dept Environm Water & Agr Engn Fac Civil & Environm Engn IL-32000 Haifa Israel Univ Calif Berkeley Dept Ind Engn Berkeley CA 94720 USA

ISBN: (纸本)9780819494290

Video tracking is a fundamental problem in computer vision with many applications. The goal of video tracking is to isolate a target object from its background across a sequence of frames. Tracking is inherently a three dimensional problem in that it incorporates the time dimension. As such, the computational efficiency of video segmentation is a major challenge. In this paper we present a generic and robust graph-theory-based tracking scheme in videos. Unlike previous graph-based tracking methods, the suggested approach treats motion as a pixel's property (like color or position) rather than as consistency constraints (i.e., the location of the object in the current frame is constrained to appear around its location in the previous frame shifted by the estimated motion) and solves the tracking problem optimally (i.e., neither heuristics nor approximations are applied). The suggested scheme is so robust that it allows for incorporating the computationally cheaper MPEG-4 motion estimation schemes. Although block matching techniques generate noisy and coarse motion fields, their use allows faster computation times as broad variety of off-the-shelf software and hardware components that specialize in performing this task are available. The evaluation of the method on standard and non-standard benchmark videos shows that the suggested tracking algorithm can support a fast and accurate video tracking, thus making it amenable to real-time applications.

关键词： Surveillance Target Tracking network flow algorithms Motion estimation Video Compression MPEG-4

来源：评论

学校读者我要写书评

暂无评论

Optimal integrated dynamic traffic assignment and signal control for evacuation of large traffic networks with varying threat levels

Optimal integrated dynamic traffic assignment and signal con...

引用

作者： Nassir, Neema The University of Arizona

学位级别：Ph.D.

This research contributes to the state of the art and state of the practice in solving a very important and computationally challenging problem in the areas of urban transportation systems, operations research, disaster management, and public policy. Being a very active topic of research during the past few decades, the problem of developing an efficient and practical strategy for evacuation of real-sized urban traffic networks in case of disasters from different causes, quickly enough to be employed in immediate disaster management scenarios, has been identified as one of the most challenging and yet vital problems by many researchers. More specifically, this research develops fast methods to find the optimal integrated strategy for traffic routing and traffic signal control to evacuate real-sized urban networks in the most efficient manner. In this research a solution framework is proposed, developed and tested which is capable of solving these problems in very short computational time. An efficient relaxation-based decomposition method is proposed, implemented for two evacuation integrated routing and signal control model formulations, proven to be optimal for both formulations, and verified to reduce the computational complexity of the optimal integrated routing and signal control problem. The efficiency of the proposed decomposition method is gained by reducing the integrated optimal routing and signal control problem into a relaxed optimal routing problem. This has been achieved through an insight into intersection flows in the optimal routing solution: in at least one of the optimal solutions of the routing problem, each street during each time interval only carries vehicles in at most one direction. This property, being essential to the proposed decomposition method, is called "unidirectionality" in this dissertation. The conditions under which this property exists in the optimal evacuation routing solution are identified, and the existence of unidirectional

关键词： Evacuation network flow algorithms Point-Queue and Spatial-Queue System Optimal Dynamic Traffic Assignment Traffic Signal Optimization Civil Engineering Cell Transmission Model

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Concave Generalized flows with Applications to Market Equilibria

Concave Generalized Flows with Applications to Market Equili...

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

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

ISBN: (纸本)9781467343831

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 [1] and Shigeno [2]. We give a polynomial time combinatorial algorithm for solving corresponding flow maximization problems, finding an epsilon-approximate solution in O(m(m + log n) log(MUm/epsilon)) arithmetic operations and value oracle queries, where M and U are upper bounds on simple parameters. This also gives a new algorithm for linear generalized flows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg, Plotkin and Tardos [3], 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 [4].

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

来源：评论

学校读者我要写书评

暂无评论

Finding Integer Efficient Solutions for Multiple Objective network Programming Problems

引用

networkS 2011年第4期57卷 362-375页

作者： Sun, Minghe Univ Texas San Antonio Dept Management Sci & Stat Coll Business San Antonio TX 78249 USA

For many practical multiple objective network programming (MONP) problems, only integer solutions are meaningful and acceptable. Representative efficient solutions are usually generated by solving augmented weighted Tchebycheff network programs (AWTNPs), sub-problems derived from MONP problems. However, efficient solutions generated this way are usually not integer valued. In this study, two algorithms are developed to construct integer efficient solutions starting from fractional efficient solutions. One algorithm finds a single integer efficient solution in the neighborhood of the fractional efficient solution. The other enumerates all integer efficient solutions in the same neighborhood. Theory supporting the proposed algorithms is developed. Two detailed examples are presented to demonstrate the algorithms. Computational results are reported. The best integer efficient solution is very close, if not equal, to the integer optimal solution. The CPU time taken to find integer efficient solutions is negligible, when compared with that taken to solve AWTNPs. (C) 2010 Wiley Periodicals, Inc. networkS, Vol. 57(4), 362-375 2011

关键词： network flow algorithms multiple objective programming multiple criteria decision making integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：