摘要:

AbstractAn algorithm for improving storage utilization for nonadaptive routing tables in point‐to‐point networks is presented. It allows storage vs. access time tradeoffs. The algorithm is quite general, and it can be used for other applications to improve storage in tree‐like structures. The algorithm was applied to the UUCP routing tables resulting in a threefold storage improv

ISSN:0028-3045    

DOI:10.1002/net.3230180402

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractWe present a general scheme for improving the asymptotic behavior of a given nonlinear programming algorithm without incurring a significant increase in storage overhead. To enhance the rate of convergence we compute search directions by partially solving a sequence of quadratic programming (QP) problems as suggested by Dembo [6]. The idea is illustrated on a class of extremely large nonlinear programming problems arising from traffic equilibrium calculations using both the Frank‐Wolfe and PARTAN algorithms to partially solve the QP subproblems. Computational results indicate that the convergence rate of the underlying algorithm is indeed enhanced significantly when Frank‐Wolfe is used to solve the QP subproblems but only marginally so in the case of PARTAN. It is conjectured, and supported by the theory [11], that with better algorithms for the QP subproblems the improvements due to the proposed framework would be more mar

ISSN:0028-3045    

DOI:10.1002/net.3230180403

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractWe consider the polymatroidal flow network model which incorporates two important extensions of the standard maximal flow problem: general concave objective functions of the vector of supplies to a collection of sinks, as well as polymatroidal capacity restrictions on sets of arcs emanating from or pointing to a common node. A number of important applications are reviewed. We show that in this general model the set of feasible supply vectors is itself a polymatroid, and that an optimal solution may be determined by at most 2|V*| — 1 maximum flow computations and optimizations of the objective over a single budget constraint, where |V*| is the number of sinks. Also, it is shown that for the most common types of polymatroidal structures an equivalent flow network can be constructed on an expanded graph but with capacity restrictions on individual arcs only. This transformation allows for the use of classical maximum flow procedures resulting in an often dramatic reduction in complexit

ISSN:0028-3045    

DOI:10.1002/net.3230180404

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractA single‐source single‐sink dynamic network is considered where the link flows are real‐valued measurable functions defined on a time interval and where storage is allowed at the nodes. Piecewise‐constant link and storage capacities are given. A τ‐maximum flow is a dynamic flow assignment that maximizes the total amount of commodity reaching the sink before time τ. The problem considered is that of computing a flow which is simultaneously τ‐maximum for all τ. Such a flow solves a minimum‐delay dynamic routing problem. An algorithm is presented which computes an optimal flow inO( |N|4T4) time, where |N| is the number of nodes andTis the number of times that the capacities change. Previous polynomial‐time algorithms have been given only for the case of

ISSN:0028-3045    

DOI:10.1002/net.3230180405

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

摘要:

AbstractGossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting one individual has an item of information which needs to be communicated to everyone else. We review the results that have been obtained on these and related problems.

ISSN:0028-3045    

DOI:10.1002/net.3230180406

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230180401

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1988

数据来源: WILEY