摘要:

AbstractThe following is a valid model for an important class of scheduling and routing problems. A salesman who travels between pairs of cities at a cost depending only on the pair, gets a prize in every city that he vitis and pays a penalty to every city that he fails to visit, wishes to minimize his travel costs and net penalties, while visiting enough cities to collect a prescribed amount of prize money. We call this problem the Prize Collecting Traveling Salesman Problem (PCTSP). This paper discusses structural properties of the PCTS polytope, the convex hull of solutions to the PCTSP. In particular, it identifies several families of facet defining inequalities for this polytope. Some of these inequalities are related to facets of the ordinary TS polytope, others to facets of the knapsack polytope. They can be used in algorithms for the PCTSP either as cutting planes or as ingredients of a Lagrangean optimand.

ISSN:0028-3045    

DOI:10.1002/net.3230190602

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

年代:1989

数据来源: WILEY

摘要:

AbstractA quadratic black box is a two‐port network with each arc incurring a quadratic cost. This paper studies the properties of the minimum cost function of a quadratic black box with respect to an external flow input. An algorithm is presented with a numerical example for determining the subdifferential mapping of the minimum cost function. The algorithm can be applied to the piecewise quadratic case without change. If all data satisfy the commensurability condition, the algorithm terminates in a finite number of step

ISSN:0028-3045    

DOI:10.1002/net.3230190603

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

年代:1989

数据来源: WILEY

摘要:

AbstractWe consider the following graph labeling problem, introduced by Leung et al. (J. Y‐T. Leung, O. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem.SIAM J. Comput.13(1984) 650–667). LetGbe a graph of ordern, andfa bijection from V(G) to the integers 1 throughn.Let |f|, and defines(G), the separation number ofG, to be the maximum of |f| among all such bijectionsf. We first derive some basic relations betweens(G) and other graph parameters. Using a general strategy for analyzing separation number in bipartite graphs, we obtain exact values for certain classes of forests and asymptotically optimal lower bounds for grids and hypercu

ISSN:0028-3045    

DOI:10.1002/net.3230190604

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

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190605

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

年代:1989

数据来源: WILEY

摘要:

AbstractBroadcast is the task of transmitting a message originated at a node in a network to all the other nodes. In this paper, we consider the problem of constructing minimal broadcast networks, that is, communication networks such that broadcast can be performed, from any node, in minimum time. The algorithms we propose allow us to improve known bounds on the minimum number of communication lines needed in minimal broadcast networks. We give some numerical evidence that our algorithms also perform well in practice.

ISSN:0028-3045    

DOI:10.1002/net.3230190606

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

年代:1989

数据来源: WILEY

摘要:

AbstractWe compare the performance of network flow algorithms based on Dinic's layered graph approach to the new Goldberg‐Tarjan (GT) algorithm. We show that for networks with small capacities, in particular for unit networks, the Dinic‐like algorithms are asymptotically faster than the GT algorithm. A second setting that we study is parameterized flow computations. Gallo, Grigoriadis, and Tarjan have shown that the GT algorithm solves this type of problem very efficiently. We show that traditional implementations of the Dinic‐like algorithms are much less efficient for solving parameterized flow problems. We also give a new implementation of a Dinic‐like algorithm that is competitive with the GT algorithm on parameterized flow n

ISSN:0028-3045    

DOI:10.1002/net.3230190607

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

年代:1989

数据来源: WILEY

摘要:

AbstractThe advance in VLSI technology and the continuing decline in the cost of computer hardware have made the construction of complex networks with many processors economically feasible. Due to the complexity of such systems, reliability has become a major issue. In some applications, it is critical that the system must be able to operate correctly despite the presence of certain faults. Multiprocessor networks with such capability are called fault‐tolerant networks. These networks increase reliability by replicating some of the basic components, i.e., by including spare processors and interconnection links. The problem that arises naturally is that of minimizing the spare components that are needed to tolerate failure. In this paper, we consider this problem when the network under consideration is organized in the form of a star. The paper describes how to design optimalm‐FT (m‐fault‐tolerant) graphs with respect to the star configuration, for all values

ISSN:0028-3045    

DOI:10.1002/net.3230190608

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

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper considers the problem of locating a single facility on a network that operates as anM/G/kqueue, in which the average queueing delay is approximated by using a result in Nozaki and Ross [J. Appl. Prob.15(1978) 826–834]. Special consideration is given to the case of a tree network. Localization and sensitivity results are provided, together with appropriate intuitive explanations. We present an illustrative numerical example and provide a brief discussion of our computational experiences with the model. We also use discrete‐event simulation to test the effectiveness of the Nozaki and Ross approximation in the context of finding a good facility location—our results indicate that their approximation is adequate for this pu

ISSN:0028-3045    

DOI:10.1002/net.3230190609

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

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190610

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

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190611

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

年代:1989

数据来源: WILEY